Вычислительная математика лекции

2n 1

12.4. Методы отыскания решений нелинейных уравнений.

12.4.1 Метод бисекции.

Описание метода.

Пусть вычислен исходный отрезок локализации [a0, b0], задана погрешность ε.Последовательность действий задается следующим алгоритмом.

1.Вводят исходные данные: f(x), a=a0, b0=b, ε.

2.Рассчитывают x=(b-a)/2.

3.Если b-a 2ε, получен результат. Вывод x.

4.Если f(a)f(x) 0, то b=x. В противном случае a=x.Возврат к пункту 2.

Графическая иллюстрация представлена на рисунке.

		x0		x1
2 (f)
	a0				b0

Скорость сходимости.

Середина n-ого отрезка дает приближение к корню x с оценкой

погрешности |xn- x | bn an b0 a0 . 2

Таким образом, метод сходится со скоростью геометрической погрешности, знаменатель которой равен q=1/2.

Влияние вычислительной погрешности.

151

В процессе вычислений важно правильно определять знак функции.

Если очередное приближение попадает в интервал неопределенности, нет гарантии правильности знака. Метод очень надежен. Гарантирует точность, равную радиусу неопределенности.

12.4.2 Метод простых итераций.

Описание метода.

Задача f(x)=0 преобразуется к виду x=φ(x). Итерационный процесс

строится по закону xn+1=φ(xn ), n=0,1,… . При удачном выборе φ(x) xn→ x , если n→∞.

Графическая интерпретация.

Корень уравнения x=φ(x) есть точка пересечения графиков y=x и

y=φ(x)

152

a), c) процесс сходится при любом начальном приближении x0, |φ'(x)|<1.

b), d) процесс расходится при любом начальном приближении x0, |φ'(x)|>1.

Сходимость.

Так как x =φ( x ), то xn+1- x = φ(xn) – φ( x )=φ'(ξn)(xn- x ).

|xn+1- x | |φ'(ξn)| |(xn- x )|. Таким образом, условие линейной сходимости |φ'( x )| =q<1 ( '(x) '( )) .

Критерий окончания.

153

xn- x ≈φ'( x )(xn-1- x )=φ'( x )[(xn- x )+(xn-1-xn)].

Следовательно, xn- x ≈[φ'( x )/(1-φ'( x ))](xn-1-xn) и

|xn- x | [q/(1-q)]|xn-1-xn|.

Критерий останова по заданной погрешности имеет вид

|xn-1-xn| ε(1-q)/q.

Замечания.

1. Часто используют критерий останова |xn-1-xn|<ε. Это оправдано,

если q 1/2. В случае ½<q<1 использование критерия может привести к преждевременной остановке вычислений.

2. Для экспериментальной оценки q можно использовать соотношение |xn-1-xn|=|φ(xn-1) – φ(xn-2)| q|xn-1-xn-2|, q≥|xn-1-xn|/|xn-1-xn-2|.

Приведение уравнения к виду, удобному для итераций Основным критерием является условие q<1.Иногда исходная

функция разрешима относительно x. В самом общем случае возможна запись x=x-w(x)f(x), w(x)≠0 x [a,b]. Простейшим вариантом является: x=x-αf(x).

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

Основной метод. Обладает квадратичной сходимостью, однако требует достаточно точного начального приближения. Для отыскания начального приближения иногда приходится использовать менее точные вспомогательные методы (например, метод бисекции).

Описание метода.

Это итерационный метод, очередной член итерационной последовательности которого находится решением линейного уравнения,

полученного в результате линеаризации функции f(x).

Пусть имеется найденное приближение xk. Пытаемся найти малую

добавку Δx такую, чтобы xk+Δx= x . Для её определения запишем

154

уравнение f(xk+Δx)=0. Используя предположение о малости Δx, его можно линеаризовать, разложив функцию в ряд Тэйлора по Δx.

f(xk+Δx )=f(xk )+f'(xk )Δx + 12 f ''( ) (Δx)2=0. f(xk )+f'(xk )( x -xk) + 12 f ''( ) ( x -xk)2=0 (*)

Пренебрегая б. м. высших порядков по Δx, имеем линейное уравнение, решением которого в силу его приближенности является не Δx,

но очередное приближение Δxk+1=xk+1-xk к x f(xk )+f'(xk )Δxk+1=0

f(xk )+f'(xk )(xk+1-xk)=0 (**)

Вычислительный алгоритм в первом приближении имеет вид. 1.Задаемся начальным приближением x0.

2. Вычисляем f(x0 ) и f'(x0 ).

3.Решаем линейное уравнение f(x0 )+f'(x0 )Δx=0.

4.Находим уточненное приближение x= x0+Δx

5.Проверяем критерий окончания вычислений |x-x0| εзад.

6.Если критерий выполнен, x найденное решение. Иначе x0=x и

переход к п.2.

Требуется уточнить несколько моментов.

1.Как выбирать x0.

2.Требует доказательства справедливость критерия останова. 3.Должна быть установлена сходимость метода.

Сходимость метода.

Теорема. Пусть x простой корень уравнения .

Предположим, что в некоторой ϭ - окрестности x : |x- x |<ϭ

выполнены следующие условия:

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

155

2. Имеют место оценки |f'(x)| c1; |f''(x)|

c2. Отметим, что c1≠0, так

как x простой корень.

Тогда, если начальное приближение x0

достаточно близко к x , метод

сходится и имеет место квадратичная скорость сходимости.

Замечание. Выражения "некоторая окрестность", "x0 достаточно

близко к x " поясняются в ходе доказательства.

Доказательство.

Вычитая (**) из (*), получаем

f'(xk )(xk+1-

) =

1

f ''( ) (

-xk)2

x

x

2

1

(xk+1-

x

) =[

f ''( ) /f'(xk )](

x

-xk)2 .

2

C|xk-

|2 , C=

c2

.

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

|xk+1- x |

x

2c

1

Здесь учтены оценки производных в п.2 формулировки теоремы.

1

Имеем цепочку

|x1- x |

C|x0- x |2, |x2- x |

C|x1- x |2

(C|x0- x |)4…и

C

1

(C | x0

|)2k .

т. д. |xk- x |

x

C

Для сходимости необходимо, чтобы |xk- x | →0 при k→∞. Для этого

должно выполняться C|x0- x |=q<1. Отсюда следует требование к области ϭ

выбора начального приближения |x0- x |<1/C, то есть σ=1/C.

C|xk-

|2

Выражение |xk+1- x |

доказывает квадратичную сходимость

x

метода.

1

0

|)2k =

1

q2k <

1

Если ϥ<1, то |xk- x |

(C | x

x

q=|x0- x |(***),

C

C

C

то есть xk не выходит за пределы ϭ.

Пусть условия п.2 теоремы выполняются, когда |x0- x |<δ. Предыдущие рассуждения справедливы, если δ C1 , то есть δ - область шире ϭ - области.

156

f (xk )

В противном случае область выбора x0 следует ограничить: |x0- x | δ. При этом условие ϥ<1 будет усилено и продолжит выполняться неравенство

(***). Теперь xk не выходит за пределы δ.

Критерий останова.

Теорема. Пусть выполнены условия предыдущей теоремы и

|x0- x |<ϭ/2. Тогда для всех k 1 верна оценка |xk- x | |xk-xk-1|.

Доказательство. Отметим, что мы заведомо сузили область задания

начального приближения. Неравенство (***) продолжает выполняться, т.е.

1

|xk- x | <|x0- x |<ϭ/2= 2C .

Из цепочки неравенств: 2|xk+1- x | 2C|xk- x |2 |xk- x | |xk-xk+1|+|xk+1- x |

следует оценка, заявленная в условиях теоремы.

Модификации метода Ньютона.

Усовершенствования направлены на решение двух основных проблем:

1.Критичность выбора начального приближения x0 (сложность оценки области сходимости метода);

2. Необходимость на каждом итерационном шаге вычислять помимо f(xk) также и ее производную f'(xk).

Для частичного решения первой проблемы предлагают видоизменить формулу метода, добавив коэффициент αk<1

xk 1 xk i f '(xk ) .

i

Вначале выбирают минимальное значение i=0, 1, 2, … и α ≈ 1 , i

2

удовлетворяющее условиям сходимости Факт сходимости устанавливается экспериментально. После осуществления достаточного

157

количества итераций, когда оказывается |xk- x | σ, переходят к основной формуле метода, полагая αi=1.

Вторая проблема снимается, если положить f '(xk)=f '(x0). Однако в этом случае скорость сходимости становится линейной.

Иногда сложно, а порой и невозможно, получить аналитическое

выражение производной. Тогда имеет смысл использовать её конечно-

разностную аппроксимацию:

f '(x )	f (zk ) f (xk )	, где z		x .
			k
k	zk xk			k
Если zk	xk 1 , формула метода приобретает вид
	xk 1 xk k			xk 1 xk		f (xk ) .
				f (x	) f (x )
				k 1	k

Метод становится двухшаговым. Его название – метод секущих.

Порядок сходимости p		5 1	.
		2
В методе Стеффенсона полагают zk xk f (xk ) . Условие zk				xk
выполняется, если приближение xk близко к корню. Этот метод
одношаговый, скорость его сходимости p=2.

Метод ложного положения получают, если zk c , где

с фиксированная точка в окрестности корня. Скорость сходимости метода линейная.

Доп. замечания.

1.При каких условиях сходимость метода становится глобальной?

Утверждение. Пусть уравнение f(x)=0 имеет корень x , функция f(x)

дважды непрерывно дифференцируема на всей числовой оси, а её первая и вторая производные знакопостоянны. Тогда метод Ньютона сходится при любом начальном приближении x0, причем, начиная с к=1,

последовательность сходится монотонно с той стороны от корня, где f(x) f''(x) >0.

158

2.Уточнение метода Ньютона для случая кратного корня.

В принципе для вычисления корня уравнения f(x) =0 кратности m можно использовать стандартный метод Ньютона. Однако в этом случае скорость сходимости оказывается только линейной, причём знаменатель

соответствующей геометрической прогрессии q 1 m1 . Для сохранения

квадратичной скорости сходимости метод нужно модифицировать

следующим образом x	x	m	f (xk )	, k 0.
k 1	k		f '(xk )

13.Методы отыскания решений систем нелинейных уравнений.

13.1. Постановка задачи.

Требуется вычислить корни системы из n уравнений с n

неизвестными

f1 (x1, x2 ,..., xn ) 0 f2 (x1, x2 ,..., xn ) 0

...............................

fn (x1, x2 ,..., xn ) 0

Матричная запись F(x)=0, x=(x1, x2,…,xn)T, F=(f1, f2,…,fn)T.

Ограничимся отысканием вещественных корней.

Понятие сходимости легко обобщается для системы, если рассматривать сходимость последовательности векторов по норме

||xk||→|| x ||, если k→∞. Аналогичным образом обобщаются формулы,

вводящие понятие скорости и порядка сходимости. Рассуждения об обусловленности скалярной задачи распространяются на систему, если воспользоваться разложением вектор – функции F(x) в ряд Тэйлора и заменить |f'(x)| на норму матрицы Якоби ||Fx (x)||.

159

13.2. Разложение в ряд Тэйлора вектор - функции F=(f1, f2,…,fn)T.

Ряд Тэйлора для скалярной функции f(x) нескольких переменных

(x=(x1, x2,…,xn)T) с остаточным членом имеет следующий вид

f(x)=f(x1,x2,…,xn)=f(x0) +[ f (x0 ) x f (x0 )

x

...

f (x0 ) x ] +

x1

1

x2

2

n

xn

1

[(

2 f (u)

(x )2

2 f (u)

x x

...

2 f (u)

x x ) …+

x 2

x x

x x

2

1

1 2

1

n

1

1

2

1

n

(

2 f (u)

x x ...

2 f (u)

(x )2 ...

2 f (u)

x x ) …+

x x

x 2

x x

k

1

k

k

n

k 1

k

k

n

(

2 f (u)

x

x

...

2 f (u)

(x )2 )].

x

x

x 2

n

1

n

n

1

n

1 x1

x=x0+Δx, u x0

i xi

, 0<θi<1. ∆xi=xi-x0.

n

x

n

В матричной форме это можно записать следующим образом f(x)=f(x0)+fx(x0)Δx+(1/2)fxx (u)Δx2 . Вектор u лежит в окрестности

точки x0, fx=( fx1, fx2,…, fxn) – вектор – строка размером (1×n), fxx= (fx )x =((fx1)x, (fx2)x,…,(fxn)x) – вектор – строка размером (1×n2),

	x1 x
	x x		всего n2	компонентов, xi – i-ая компонента
x2	2
	xn x

вектора x.

Если речь идет о вектор – функции, то

F(x)=F(x0)+Fx(x0)Δx+(1/2)Fxx(u) Δx2 , где Fx(x0) – матрица Якоби размера

(n×n), Fxx(u) – матрица размера (n×n2). Заметим, что || Δx2 ||∞ = || Δx ||2∞ .

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

Все рассуждения и доказательства, сделанные при обосновании метода для скалярного варианта, переносятся на систему уравнений,

160