Методичка (864359), страница 4
Текст из файла (страница 4)
1.5.122231 10 50 –60 01 7 0 0 | –167 –10 –5 0 | 460 7 3 –10 | 620 0 7 1 | –6625240 0|01 0|97 –9 | –1149 1 | –482617004 0 0 | –159 4 0 | 185 –10 –3 | –1190 9 1 | 7128271 2 0 0 | –5–10 7 8 0 | –420 –1 3 –3 | 100 0 –4 1 | –8291 102 –90 50 00 0 | 719 0 | –1427 –2 | –266 1 | –551 9 0 0 | 870 –2 –10 0 | 620 9 –7 –10 | 1970 0 8 1 | –701 –5–1 90 –70 00–6–2100 | –280 | 583 | –611 | –171 9 01 –1 –20 –8 50 0 –10 | –490 | 137 | 291 | –13018007 0 0 | –437 7 0 | –714 9 –6 | –1540 –3 1 | 361.6. Численные методы решениясистем нелинейных уравненийМетод последовательных приближенийРассмотрим уравнение видаx = ϕ( x ).Построим графики функций обоих частей уравнения (рис.
1.6.1).Решением уравнения является абсцисса x* точки пересеченияграфика функции ϕ( x) и биссектрисы y = x. Точек пересечения x*может быть несколько. Допустим, что для точного решения x* каким-либо способом указано начальное приближение x0. В простейшем методе итераций все дальнейшие итерации строятся поформуле:x n +1 = ϕ( x n ), n = 0, 1, 2, ... .Этот процесс(см. рис. 1.6.1).называетсяпростойодношаговойитерацией31Рис. 1.6.1.
Иллюстрация метода последовательных приближенийВыясним поведение приближений xn, когда они находятсявблизи решения x*. Удобнее иметь дело не с приближениями xn,а с их погрешностями εn = x* – xn, так как это дает право воспользоваться малостью εn:x n+1 = x* − ε n+1 = ϕ( x n ) = ϕ( x* − ε n+1 ) = ϕ( x* ) − ϕ′( x* ) + 0(ε n ).Следовательно, ε n+1 ≈ εn ϕ′( x n ).Рассмотрим три случая.1. При ϕ′( x* ) > 1 погрешность εn+1 по абсолютному значениюбольше погрешности εn, и приближение x n +1 будет отстоять от точного решения x* дальше, чем результат xn.
Решение x* будет «точкойотталкивания» для приближений, близких к x*, и в этом случае небудет сходимости приближения xn к точному решению x*.2. Если ϕ′( x* ) < 1 , то ε n +1 < εn , поэтому при начальном приближении x0, достаточно близком к x*, xn сходится к точному решению x* примерно со скоростью геометрической прогрессии сознаменателем q = ϕ′( x* ) . При ϕ′( x* ) > 0 погрешности εn+1 и εn бу32дут иметь одинаковые знаки и сходимость будет монотонной. Когда же ϕ′( x* ) < 0 , погрешности εn+1 и εn имеют разные знаки и приближение xn будет сходиться к точному решению x*, колеблясьоколо x*. Интервал колебаний часто позволяет оценить точностьвычислений.→ 0 со скоростью, пре3.
При ϕ′( x* ) = 0 погрешность ε n ⎯⎯⎯n→∞восходящей сходимость геометрической погрешности со скольугодно малым знаменателем.Для решения системы уравнений методом итераций преобразуем ее к виду x = Φ ( x ) , илиx1 = Φ1 ( x1 , ..., xm );x2 = Φ 2 ( x1 , ..., xm );…xm = Φ m ( x1 , ..., xm ).При этом итерации проводят по формулеx n+1 = Φ ( x n ),илиxin+1 = Φi ( x1n , x2n ,..., xmn ), i = 1, 2, ..., m.Перейдем к изучению метода с более общих позиций.Определение. Пусть Х — полное нормированное пространство(т. е.
пространство, в котором сходится любая фундаментальнаяпоследовательность), например Rn, а оператор y = Φ( x) отображает Х в себя. Если при некотором значении 0 ≤ q < 1 при всех значениях x1 , x2 ⊂ XΦ ( x1 ) − Φ( x2 ) ≤ q x1 − x2 ,то такое отображение называется сжимающим.Теорема (принцип сжимающих отображений). Если отображение y = Φ (x) сжимающее, то уравнение y = Φ (x) имеет единственное решение x * и33x* − x k ≤qkx1 − x 0 .1− qДоказательство. Из определения имеемx n+1 − x n = Φ( x n ) − Φ ( x n−1 ) ≤ q x n − x n−1 ,следовательно,x n+1 − x n ≤ q n x1 − x 0 = q n a.Пусть l > n. Тогда из свойств нормированного пространстваимеем∞xl − x n ≤ x l − xl −1 + ...
+ x n+1 − x n ≤ ql −1a + ... + q n a ≤ q n a∑ ql =l =0qna.1− qТаким образом, последовательность xn фундаментальна. Покажем единственность неподвижной точки. Допустим, что их две: x*и y*. Тогдаx* − y* = Φ ( x* ) − Φ ( y* ) ≤ q x* − y * ,т. е. пришли к противоречию.Замечание. Сжимаемость оператора Ф необходима лишь в некоторой окрестности точки x*. В достаточно малой окрестностирешения x * ∈ R m системы для приближения методом простых итераций имеемx n+1 − x * = Φ ( x n ) − Φ ( x * ) ≈ Φ′( x * )( x n − x * ),где⎛ ∂Φ1⎜ ∂x⎜ 1Φ′( x * ) = ⎜⎜⎜ ∂Φ m⎜ ∂x⎝ 1— матрица Якоби.34∂Φ1 ⎞∂xm ⎟⎟⎟⎟∂Φ m ⎟∂xm ⎟⎠Следовательно, если Φ′( x * ) < 1, то можно ожидать сходимости итерационного процесса при условии, что итерации x n неочень далеки от точного решения.Метод НьютонаЕсли известно довольно хорошее начальное приближение кточному решению x * системы уравненийF ( x ) = 0,то эффективным методом повышения точности численного решения является метод Ньютона.
Идея метода Ньютона заключается втом, что в окрестности имеющегося приближения x n задачу заменяют некоторой вспомогательной линейной задачей.Рассмотрим уравнение f ( x) = 0 :f ( x ) ≈ f ( x n ) + f ′( x n )( x − x n ) = 0.Его решениеx = xn −f (xn )f ′( x n )принимают за следующее приближение, т. е.xn +1f (x n ).=x −f ′( x n )nДля пояснения итерационного процесса запишем уравнение касательной к функции f ( x ) в точке x0:y − f ( x 0 ) = f ′( x 0 )( x − x 0 ).Если положить y = 0, то получимx = x0 −f ( x0 ),f ′( x 0 )поэтому метод Ньютона называют еще методом касательных.35Рассмотрим общий случай. Пусть отображение F : R m → R m .Тогда−1x n +1 = x n − ⎡⎣ F ′( x n ) ⎤⎦ F ( x n ).{}Пусть Ω a = x : x − x * < a . И пусть при некоторых значениях a,a1, a2, a > 0, a1 ≥ 0, a2 < ∞ выполнены условия:1)[ F ′( x )]−1≤ a1 при x ∈ Ω a ;2) F (u1 ) − F (u2 ) − F ′(u2 )(u1 − u2 ) ≤ a2 u2 − u12при u1, u2 ∈ Ωa ⊂ R n.Обозначим c = a1a2 , b = min(a, c −1 ).Условие 2 автоматически выполняется, если функции имеютограниченные вторые производные, так как по формуле Тейлора(∂Fi ( x1 ...xm )( yj − xj ) + O y − x∂x jj =1mFi ( y ) = Fi ( x ) + ∑2).Теорема (о сходимости метода Ньютона).
При выполненииусловий 1, 2 и x ∈ Ωb итерационный процесс Ньютона вида−1x n +1 = x n − ⎡⎣ F ′( x n ) ⎤⎦ ⋅ F ( x n )сходится с оценкой погрешности(x n − x * ≤ c −1 c x 0 − x *)2n.Доказательство. Пусть начальное приближение x 0 ∈Ωb . По-кажем, что если итерация x n ∈ Ωb , то и итерация x n+1 ∈ Ωb . Пустьu1 = x * , u2 = x n . Тогда2F ( x * ) − F ( x n ) − F ′( x n )( x * − x n ) ≤ a2 x n − x * .Поскольку F ( x n ) = − F ′( x n )( x n +1 − x n ), F ( x * ) = 0, то362F ′( x n )( x n+1 − x * ) ≤ a2 x n − x * .Следовательно, имеем−1x n +1 − x * ≤ ⎡⎣ F ′( x n ) ⎤⎦ ⋅ F ′( x n )( x n +1 − x * ) ≤≤ ⎡⎣ F ′( x n ) ⎤⎦−1⋅ F ′( x n )( x n +1 − x * ) ≤ a1 a2 x n − x *2=2= c x n − x * . (1.6.1)Отсюдаx n +1 − x * ≤ cb 2 = (cb)b ≤ b,так как cb < 1 , поэтому x n+1 ∈ Ωb .
Получаем, что все итерацииx n ∈ Ωb , так как x 0 ∈Ωb .Пусть qn = c x n − x * . После умножения на с неравенство(1.6.1) примет видqn+1 ≤ qn2 .nСледовательно, qn ≤ (q0 ) 2 и(c x n − x* ≤ c x 0 − x*)2n.Теорема доказана.Мы видим, что итерации сходятся с квадратичной скоростью.Это придает методу Ньютона особую ценность.Покажем, как избежать обращения матрицы при использовании метода Ньютона:F ′( x n ) = ( x n +1 − x n ) = − F ( x n );z n +1 = x n +1 − x n ;F ′( x n ) z n = − F ( x n );x n +1 = x n + z n .37Таким образом, метод Ньютона сведен к решению системы линейных уравнений на каждом шаге итераций.Пример. ПустьF1 ( x1 , x2 ) = x12 + x2 2 − 1;F2 ( x1 , x2 ) = x12 − x2 ;x10 = 0,5;x20 = 0,5.Имеем⎛ 2 x1 2 x2 ⎞F ′( x ) = ⎜⎟;⎝ 2 x1 −1 ⎠( F ′( x ) )−1=1−2 x1 − 4 x1 x2⎛ x1n +1 ⎞ ⎛ x1n ⎞1⎜ n +1 ⎟ = ⎜ n ⎟ −⎝ x2 ⎠ ⎝ x2 ⎠ −2 x1 − 4 x1 x2⎛ −1⎜⎝ −2 x1⎛ −1⎜n⎝ −2 x1−2 x2 ⎞⎟;2 x1 ⎠−2 x2n ⎞ ⎛ ( x1n )2 + ( x2n )2 − 1⎞⎟⎜⎟.2 x1n ⎠ ⎝ ( x1n ) 2 − ( x2n ) ⎠Модифицированный метод НьютонаПри использовании модифицированного метода Ньютона походу вычислений выбирают или заранее задают некоторую последовательность чисел: n0 = 0, n1 , n2 , ...
При nk ≤ n < nk +1 итерациипроизводят по формуле(x n +1 = x n − F ′( x nk ))−1F ( x n ).Увеличение числа итераций, сопровождающее такую модификацию,компенсируется большей «дешевизной» одного шага итерации.Метод секущихДля решения одного скалярного уравнения f ( x) = 0 наряду сметодом Ньютона применяют метод секущих. Простейший вари38ант этого метода заключается в следующем. В процессе итерацийфиксируют некоторую точку x0. Приближение xn+1 находят какабсциссу точки пересечения прямой, проходящей через точки( x 0 , f ( x 0 )), ( x n , f ( x n )), с осью Ox . При этомx n+1 = x n −f ( x n )( x n − x 0 ).f ( x n ) − f ( x0 )Более эффективен способ, где за приближение x n +1 принимаютабсциссу точки пересечения с осью Ox прямой, проходящей черезточки ( x n−1 , f ( xn−1 )), ( x n , f ( xn )), при этомx n +1 = x n −f ( x n )( x n − x n −1 ).f ( x n ) − f ( x n −1 )Задание к лабораторной работе«Численные методы решения систем нелинейных уравнений»1.
Решить аналитически систему уравнений.2. Решить графически систему уравнений (варианты 1–22 втабл. 1.6.1) с помощью программы построения графиков функций.3. Написать программу решения системы уравнений методомНьютона. В качестве начального приближения взять результатыграфического решения. Сравнить результаты аналитического играфического решений.4. Оформить отчет о лабораторной работе:1) теоретическая часть;2) графическое решение системы нелинейных уравнений;3) текст программы;4) результаты.39Таблица 1.6.1Варианты (1–30) систем нелинейных уравнений1x 2 + y 2 − 4 = 0,2x 2 + y 2 − 4 = 0,x − y2 −1 = 0x2 − y − 1 = 03( x 2 + y 2 ) 2 − 4( x 2 − y 2 ) = 0,4x + y + xy − 7 = 0,x2 + y 2 − 1 = 0x 2 + y 2 + xy − 13 = 053 x 2 + 5 xy − 2 y 2 − 20 = 0,62 x 2 + xy − y 2 − 20 = 0,x 2 + xy + y 2 − 7 = 0x 2 − 4 xy + 7 y 2 − 13 = 07x 2 − y 2 + 3 y = 0,8( x + y )( x 2 − y 2 ) − 16 = 0,x 2 + 3 xy + 2 y 2 + 2 x + 4 y = 0( x − y )( x 2 + y 2 ) − 40 = 09( x + y )( x + 2 y )( x + 3 y ) − 60 = 0,( y + x)( y + 2 x )( y + 3 x ) − 105 = 010x 4 + 6 x 2 y 2 + y 4 − 136 = 0,1110 x 2 + 5 y 2 − 2 xy − 38 x − 6 y + 41 = 0,12x3 + y 3 − 19 = 0,( xy + 8)( x + y ) − 2 = 03 x 2 − 2 y 2 + 5 xy − 17 x − 6 y + 20 = 013x 2 y 2 − 2 x + y 2 = 0,14x3 + x 3 y 3 + y 3 − 17 = 0,x + xy + y − 5 = 02 x2 − 4 x + 3 + y 3 = 015( x 2 + y 2 )( x + y ) − 15 xy = 0,( x + y )( x + y ) − 85 x y = 04422x3 y + xy 3 − 30 = 02216−1 − x − 2 y − x − 1 = 0,1− 2y + 2y − x − 4 = 017log y x − 2 log x y − 1 = 0,182 2 x − 3 y + 17 = 0,x2 + 2 y 2 − 3 = 02x − 3y / 2 + 1 = 040Окончание табл.
1.6.119cos( x − y ) − 2 cos( x + y ) = 0,cos x cos y − 0, 75 = 02021sin x − sin 2 y = 0,cos x − sin y = 02223x − 2 y + 3 z − 9 = 0,x 2 + 4 y 2 + 9 z 2 − 189 = 0,3 xz − 4 y 2 = 05= 0,24 x − 3 y −1 = 0log x y + log y x −3= 0,43cos x sin y −=0424tg x tg z − 3 = 0,sin x cos y −tg y tg z − 6 = 0,x+ y+ z−π=025x y z+ + − 3 = 0,y z xy z x+ + − 3 = 0,x y zx+ y + z −3= 026( x + y ) 2 − z 2 − 4 = 0,27xy + yz − 8 = 0,yz + zx − 9 = 0,zx + xy − 5 = 0282 x + y + z = 0,3 x + 2 y + z = 0,29x + y + z − 2 = 0,30x − y + z − 6 = 0,x 2 + y 2 + z 2 − 6 = 0,x 2 + y 2 + z 2 − 14 = 0,x3 + y 3 + z 3 − 8 = 0x3 − y 3 + z 3 − 36 = 0( y + z ) 2 − x 2 − 2 = 0,( z + x) 2 − y 2 − 3 = 03( x + 2)3 + 2( y + 1)3 + ( z + 1)3 − 27 = 0412. ПРИБЛИЖЕНИЕ ФУНКЦИЙ2.1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
