Практикум j практическое примщенше численных методов

(ж = {} = {Х\ , Х2, • • . , Х_п } )

F(x) =	{/ь/г,--ч/п}	— вектор-функция с компонентами
		h> /2» • • • ? fn
	F\x)	— матрица Якоби
	х^к	— приближенное решение на к-й итерации

1. 
   Решение нелинейных уравнений и систем Ищется решение нелинейного уравнения
   

f(x) = 0, (7.1)
где f(x) — заданная функция. Корни уравнения (7.1) могут быть комплекс' ными и кратными. Выделяют как самостоятельную проблему разделения корней, когда проводится выделение области в комплексной плоскости, со- держащей один корень. После этого на основе тех или иных итерационны* процессов при выбранном начальном приближении находится решение нелИ' нейного уравнения (7.1).
В более общем случае мы имеем не одно уравнение (7.1), а систему нелиней­ных уравнений
/г(.г-1, г'2, •.., г*_п) =0, i = 1,2,..., п. (7-2)
Обозначим через х — {ад, х₂₎..., г_п} вектор неизвестных и определим вектор- функцию F(.x) = {/ь/2, • • •,/п}. Тогда система (7.2) записывается в виде уравнения
F(x) = 0. (7.3)
Частным случаем (7.3) является уравнение (7.1) (n = 1). Второй пример (7.3) — система линейных алгебраических уравнений, когда F(x) = Ах - /.

2. 
   Итерационные методы решения нелинейных уравнений
   

Для приближенного решения нелинейных уравнений и систем нелинейных уравнений используются итерационные методы. Среди основных подходов можно выделить метод последовательных приближений (простой итерации) и метод Ньютона.
Алгоритмы для решения нелинейного уравнения
При итерационном решении уравнений (7.1), (7.3) задается некоторое началь­ное приближение, достаточно близкое к искомому решению х*. В одношаго­вых итерационных методах новое приближение х^к+1 определяется по преды­дущему приближению х^к. Говорят, что итерационный метод сходится с ли­нейной скоростью, если х^к+1 — х* = 0(х^к — х*) и итерационный метод имеет квадратичную сходимость, если х^к+1 — х* = 0(х^к — а;*)².
Заменим уравнение (7.1) эквивалентным уравнением
х = р(х), (7.4)
полагая, например,
(р(х) = x + g(x)f(x),
где функция д(х) не меняет знака на отрезке, на котором ищется решение уравнения (7.1). Для приближенного решения уравнения (7.4) используется метод простой итерации, когда
х^к+1=ф^к), к = 0,1,... (7.5)
при некотором заданном начальном приближении х°.
Пусть в некоторой окрестности R = {х | \х — ж*| < г} корня х = х* уравнения (7.4) функция (р(х) удовлетворяет условию Липшица
\
(7.6)

ч>{х) - у(у)| < q\x - у\ х,у G R
с постоянной q < 1. Тогда метод простой итерации (7.5) сходится и для ц₀, грешности верна оценка
\х^к-x*\^k\x°-х*\. (7.7)
Можно сформулировать условия, гарантирующие, что имеется единственный корень в окрестности начального приближения х°. Пусть теперь R = {х | х°\ < г} и
к⁰ - Ф°)\ < (1 - ч)г, (7.8)
тогда при выполнении (7.6) с q < 1 уравнение (7.4) имеет единственное ре­шение в R.
В
Jf+i


/(**)
f'{x^kY


к = 0,1,


(7.9)

итерационном методе Ньютона (методе касательных) для нового прибли­жения имеем
Пусть х* — простой вещественный корень уравнения (7.1) и определим R, = {х | \х — х*\ < г} — окрестность этого корня. Предположим также, что
i
причем


■ х*\ <


2т
Л7'

nf \ f'(x)\ = т> 0, sup \f"(x)\ = М, xeR _xGR
Тогда при х° е R метод Ньютона (7.9) сходится и для погрешности справед­лива оценка
\х^к-х*\ ^2k~^l\x^Q-x*
Тем самым метод Ньютона имеет квадратичную сходимость.
Модификации метода Ньютона направлены на минимизацию вычислитель­ной работы, на увеличение окрестности корня, в которой можно задавать начальное приближение. Примером выступает метод секущих, который по­лучается из метода Ньютона заменой производной в знаменателе на соответ­ствующую разделенную разность:
^{хМ = хк}~1Щ^^{к =} (^7л0)
Этот метод является простейшим двухшаговым итерационным методом, ко­гда новое приближение х^к+1 находится по двум предыдущим х^к и х^к~¹.
Методы решения систем нелинейных уравнений
При приближенном решении систем нелинейных уравнений (7.3) можно ори- ентироваться на аналоги метода многомерные простой итерации и метод*¹
Ныотопа. Многие одношаговые методы для приближенного решения (7.3) но аналогии с двухслойными итерационными методами для решения систем ли­нейных алгебраических уравнений можно записать в виде
j.fc+1
В_к+1 + F(x^k) = 0, * = 0,1,..., (7.11)
^тк+1
где т_к+1 — итерационные параметры, а В_к+1 — квадратная матрица п х п, имеющая обратную.
Для стационарного итерационного метода (7.11) (Вит не зависят от к) имеем
x^k+1 = S{x^k), (7.12)
где S(x) = х — тВ~¹ F(x). Тес самым (7.12) соответствует применению метода простой итерации для преобразованного уравнения
x = S(x). (7.13)
Пусть в окрестности R = {х \ \\х — х°\\ < г} заданного начального приближе­ния х° выполнены условия
||5(a:)-5(2/)|| 2/||, х,у е R,
||*°-5(х°)||<(1-1)г, д<1.
Тогда уравнение (7.13) имеет в R единственное решение х*, которое дается итерационным процессом (7.12), причем для погрешности справедлива оцен­ка
\\x^k+l-x*\\^k\\x°-x*\\.
В методе Ньютона новое приближение для решения системы уравнений (7.2) определяется из решения системы линейных уравнений
i>"⁺ⁱ - +/<(**)=°- (^?л4)
, 3 =1 ' ^J
г — 1,2,... ,п, к — 0,1, —
Определим матрицу Якоби

дШ	9fi{x)	9fi(x)
dxi	дх2	дхп
ОМх)	ОШ	9fi{x)
dxi	дх2	9хп
dfn(x)	dfn{x)	9f„{x)
dxi	Ох 2	дхп

F'(x) =

и запишем (7.14) в виде
F'(x){x^k+1 - х^к) + F(x^k) — 0, к = 0,1,.... (7.15)
При использовании записи (7.11) метод Ныотопа (7.15) соответствует выбору
В_к+1 = F'(x^k), т_к+1 = 1.
Система линейных уравнений (7.15) для нахождения нового приближении х^к+1 может решаться итерационно. В этом случае мы имеет двухступенчатый итерационный процесс со внешними и внутренними итерациями. Например, внешний итерационный процесс может осуществляться по методу Ныотопа. а внутренние итерации — на основе итерационного метода Зейделя.
При решении систем нелинейных уравнений можно использовать прямые аналоги стандартных итерационных методов, которые применяются для ре­шения систем линейных уравнений. Нелинейный метод Зейделя примени­тельно к решению (7.2) дает
0
лс
, г = 1,2,
В этом случае каждая компонента нового приближения из решения нелиней­ного уравнения, что можно сделать на основе итерационных метода простой итерации и метода Ньютона в различных модификациях. Тем самым сно­ва приходим к двухступенчатому итерационному методу, в котором внешние итерации проводятся в соответствии с методом Зейделя, в внутренние — ме­тодом Ныотопа.
Основные вычислительные сложности применения метода Ныотопа для при­ближенного решения систем нелинейных уравнений связаны с необходимо­стью решения линейной системы уравнений с матрицей Якоби на каждой итерации, причем от итерации к итерации эта матрица меняется. В модифи­цированном методе Ньютона
F'(x°)(x^k+1 - х^к) + F(x^k) = 0, к = 0,1,...
матрица Якоби обращается только один раз.

3. 
   Упражнения
   

Упражнение 7.1 Напишите программу для нахоэюдения решения нелиней­ного уравнения f(x) = 0 методом бисекций. С ее помощью найдите корна уравнения (1 + х²)е~^х + sm(x) = 0 на интервале [0,10].
В модуле bisection функция bisectionO обеспечивает нахождение корня уравнения f(x) = 0 на интервале [xi,x₂] при условии, что f(xi)f(x₂) < 0.
Модуль bisection
import numpy as np import math as mt
def bisection(f, xl, x2, tol=l.0e-10):
и и и
Finds a root of f(x) =0
between the arguments xl and x2 by bisection. f(xl) and f(x2) can not have the same signs.
и и и
fl = f(xl) f 2 = f(x2) if fl*f2 >0.:
print ’f(xl) and f(x2) can not have the same signs’ n = int(mt.ceil(mt.log(abs(x2 - xl)/tol)/mt.log(2.))) for i in range(n):
x3 = 0.5*(xl + x2) f3 = f(x3) if f 2*f3 < 0.: xl = x3 fl = f3 else:
x2 =x3 f2 = f3
return (xl + x2)/2.
Для определения интервалов, которые содержат корни уравнения f(x) = 0 будем использовать график у = f(x). С учетом этого для нахождения корней уравнения (1 + х²)е~^х + sin(:c) = 0 используется следующая программа.
import numpy as np import matplotlib.pyplot as pit from bisection import bisection def f(x):
return (1. + x**2) * np.exp(-x) + np.sin(x) x = np.linspace(0., 10., 200) у = f(x) pit.plot(x, y) plt.xlabel(’x’) pit.grid(True) pit.show()