Лекции по информатике
  • Регистрация
1 1 1 1 1 1 1 1 1 1 Рейтинг 0.00 (0 Голоса)

Лекция 5. Численное решение уравнений.

Численноерешениеуравнений

 

Общий вид уравнения φ(х) = g(x) .

 

Преобразуем φ(х)- g(x) =0 и обозначимf(x)= φ(х)- g(x), т. е.f(x) =0.

 

Уравнение f(x) =0 называется алгебраическим, если функция f(x)представляет собой многочлен;

если же в функцию f(x) входят элементарные (тригонометрические, логарифмические, показательные и т. п.) функции, то такое уравнение называется трансцендентным.

Значение x*, такое, что f(x*)=0, называется корнем уравнения.

В процессе численного решения уравнения, в общем случае, рассматриваются две задачи:

1)  отделение корней, т. е. отыскание достаточно малых областей, в каждой из которых находится один и только один корень уравнения;

2)  нахождение корня с заданной точностью.

Пусть задано уравнение f(x) =0 .

Будем полагать, что функция f(x)определена и непрерывна на некотором интервале [a,b] , внутри которого существует и находится единственный корень уравнения.

Рассмотрим три метода решения:

·  метод итераций;

·  метод Ньютона (метод линеаризации или касательных);

·  метод половинного деления (метод дихотомии).

Метод половинного деления

Метод половинного деления всегда позволяет найти решение за конечное число шагов, т. е. всегда сходится.

f(a)

 

f(b)

 

1. Делим отрезок [а,b] пополам, получаем начальное приближение (значение) корня

х0 = (а + b)/2 .

2. Если f(х0)=0, то х0 является корнем уравнения;

если f(х0)0, то выбираем тот из отрезков [а, х0]или [х0, b], на концах которого функция f(х)имеет противоположные знаки.

Для полученного отрезка повторяем указанную процедуру.

Процесс деления отрезков пополам продолжаем до тех пор, пока длина отрезка, на концах которого функция имеет противоположные знаки, не будет меньше заданной предельной допустимой погрешности ε.

Метод итераций

 

Представим уравнение в виде:

x = φ(х).

Выберем на отрезке [a,b] произвольную точку х0- нулевое приближение, и примем в качестве следующего приближения x1= φ(х0), затем x2 = φ(х1), и т. д.

Таким образом,

xn = φ(хn-1).

Процесс последовательного вычисления значений xn(n = 1, 2, 3,...) называется методом итераций.

Геометрическая интерпретация метода итераций

0 X* X2 X1 X0 b

Если на отрезке [a,b], содержащем корень х* уравнения, а также его последовательные приближения

х0, x1,..., хn,...., выполнено условие

| φ’(х)|≤q<1,

то процесс итераций сходится, т. е. увеличивая n, можно получить приближение, сколь угодно мало отличающееся от точного значения корня x*.

Для нахождения корня уравнения с заданной точностью (предельной абсолютной погрешностью) ε, процесс итераций следует продолжать до тех пор, пока для двух последовательных приближений xn-1и хnне будет обеспечено выполнение неравенства

| xn-1хn|≤((1-q) /q)×ε (*),

при этом всегда будет выполнено неравенство |х*- хn|≤ε.

Если значение q≤0,5 , то (1-q)/q≥1и вместо (*) для обеспечения требуемой точности решения можно использовать более простое соотношение

n — хn-1|ε.

Для того, чтобы привести f(x)=0 к виду x=φ(х)умножим левую и правую части уравнения на произвольную константу λи к каждой из частей прибавим x:

 

x = х+ λ f (х).

 

Тогда

φ(х)= х+ λ f (х).

Пусть

т1-наименьшее значение производной f’(х),

M1-наибольшее значение производной f’(х)на отрезке [a,b], т. е.

0<m1f’(x)M1.

 

Если выбрать

λ= 1/М1и q = 1-m1/M1 ,

то условие сходимости метода итераций будет выполнено.

Метод Ньютона

Пусть уравнение f(x)=0имеет один корень на отрезке [а, b], причем f’(х)и f’’(х)определены, непрерывны и сохраняют постоянные знаки на этом отрезке.

Геометрическая интерпретация

Выберем некоторую точку х0отрезка [а, b] и проведем в точке Р0(х0,f(х0))касательную к кривой y=f(x)до пересечения с осью 0х.

Абсцисса x1точки пересечения - первое приближение корня.

Проведем касательную через новую точку Р1(х1, f(х1))и найдем точку пересечения с осью 0х, получим второе приближение корня х2и т. д.

Уравнение касательной через точку Р0:

y= f(х0)+ f‘(х0)×(x- х0).

При y=0 находим первое приближение:

х1=х0 - f(х0)/ f’(х0).

Следующие приближения определяются формулами:

х2=х1 - f(х1)/f’(х1)

. . .

хn=хn-1 - f(хn-1)/f’(хn-1).

Процесс вычисления приближений продолжается до тех пор, пока не будет выполнено условие

| хп - хп-1 |<, (**)

где m1 - наименьшее значение |f’(x)|, а M2 - наибольшее значение |f” (x)|на отрезке [a,b].

При этом условии будет выполнено и условие |х* - хn|≤ε,

где ε - предельная абсолютная погрешность вычисления корня.

Если 2×т1/М210-2, то неравенство(**) всегда выполняется, если

nn-1|<10-1 (***).

Условие сходимости f(х0)×f(х0)> 0.

Обычно выбирают х0 = аили х0=b.

Пример1.

Задано уравнение

arcsin (2∙x+1)-x2=0.

Методом итераций найти корень, расположенный на отрезке [-0,5; 0], с абсолютной погрешностью ε =10-4.

Определить также число итераций, необходимое для нахождения корня.

Преобразуем уравнение:

arcsin (2∙x + 1) = x2

 

sin (arcsin (2∙х +1)) = sin х2

 

2∙х +1 = sin х2

 

x=0,5∙ (sin х2-1)

φ(х)= 0,5 (sin х2-1)

Найдем φ’(х):

 

 

φ’(х)=xcos х2

Очевидно, что для всех -0,5 x 0

| φ’(х)|= | xcos х2| 0,5

Процесс итераций сходится.

За начальное приближение можно принять любую точку интервала. Пусть х0 = -0,4 .

Алгоритм нахождения корня:

1. Полагаем х = -0,4; ε =0,0001 и n =0 .

2. Вычисляем следующее приближение

yпо формуле y=0,5∙ (sin х2-1) .

3. Вычисляем разность δ=y-xи увеличиваем величину nна единицу.

4.  Проверяем условие |δ | > ε. Если это условие выполняется, то переходим к п. 2, если условие не выполняется, то результатом считаем величину yи

заканчиваем вычисления.

Пример2.

Задано уравнение

sinxx+ 0,15 = 0 .

Методом Ньютона найти корень, расположенный на отрезке [0,5; 1], с абсолютной погрешностью ε =10-4.

Определить также число итераций, необходимое для нахождения корня.

Найдем f’(х)= cosx- 1 и

f’’ (х)= -sinx.

Так как f’’(х)<0 для всех 0,5 x 1, то для того, чтобы выполнялось неравенство f(х0)×f(х0)>0 надо найти значение х0 , чтобы выполнялось f(х0)<0 .

Очевидно, это выполняется при х0=1 .

 

 

Найдем

m1 - мин. зн. |f’(x)|, M2 - макс. зн.|f”(x)|на отрезке [0,5; 1].

m1 = |cos 0,5 - 1|=0,12

 

M2 = |-sin 1|=0,84

 

2×т1/М210-2

Для проверки условия прекращения вычислений можно пользоваться неравенством (***)

Алгоритм нахождения корня:

1. Полагаем х = 1; ε =0, 001 и n =0 .

2. Вычисляем следующее приближение

yпо формуле

y=x-(sin x – x + 0,15)/ (cos x – 1).

3. Вычисляем разность δ=y-xи увеличиваем величину nна единицу.

4. Проверяем условие |δ | > ε. Если это условие выполняется, то переходим к п. 2, если условие не выполняется, то результатом считаем величину yи заканчиваем вычисления.

Пример3.

Задано уравнение

x-(9+x)1/2 + x2-4 = 0.

Методом половинного деления найти корень, расположенный на отрезке [2; 3], с абсолютной погрешностью ε =10-4.

Алгоритм нахождения корня:

1. Полагаем a= 2;b=3; ε =0, 0001.

2. Вычисляем f(a)=a - (9+ a)1/2 + a 2-4.

3. Вычисляем

x=(a+b)/2 и f(x)=x- (9+x)1/2 +x 2-4.

 

4. Проверяем условие f(x)=0 . Если условие выполняется, то корень найден, иначе – п.5.

1.  Из [a; x] и [x;b] выбираем отрезок, содержащий корень: проверяем условиеf(a)∙ f( x)<0 .

Если условие выполняется, то b=xи п.6;

иначе – a= x; f(а)= f(x) и п.6.

 

6. Проверяем условие b- a>ε. Если условие выполняется, то п.3, иначе – за результат принимаем значение x.

Добавить комментарий


Защитный код
Обновить

По темам:

История Украины

Культурология

Высшая математика

Информатика

Охотоведение

Статистика

География

Военная наука

Английский язык

Генетика

Разное

Технологиеские темы

Украинский язык

Филология

Философия

Химия

Экология

Социология

Физическое воспитание

Растениевосдство

Педагогика

История

Психология

Религиоведение

Плодоводство

Экономические темы

Бухгалтерские темы

Маркетинг

Иностранные языки

Ветеринарная медицина

Технические темы

Землеустройство

Медицинские темы

Творчество

Лесное и парковое хозяйство