Нека заменим оригиналното уравнение с еквивалентно и да изградим итерации според правилото 
. По този начин методът на проста итерация е едноетапен итеративен процес. За да започнете този процес, трябва да знаете първоначалното приближение. Нека да открием условията за сходимост на метода и избора на първоначалното приближение.
Билет №29
Метод на Seidel
Методът на Зайдел (понякога наричан метод на Гаус-Зайдел) е модификация на простия итерационен метод, който се състои в това, че при изчисляване на следващото приближение x (k+1) (виж формули (1.13), (1.14)) неговата вече получените компоненти x 1 ( k+1) , ...,x i - 1 (k+1) се използват веднага за изчисляване на x i (k+1) .
В координатна нотация методът на Seidel има формата:
X 1 (k+1) = c 11 x 1 (k) + c 12 x 2 (k) + ... + c 1n-1 x n-1 (k) + c 1n x n (k) + d 1
x 2 (k+1) = c 21 x 1 (k+1) + c 22 x 2 (k) + ... + c 2n-1 x n-1 (k) + c 2n x n (k) + d 2
...
x n (k+1) = c n1 x 1 (k+1) + c n2 x 2 (k+1) + ... + c nn-1 x n-1 (k+1) + c nn x n (k ) + dn
където x (0) е някакво първоначално приближение към решението.
Така i-тата компонента на (k+1)-тото приближение се изчислява по формулата
| x i (k+1) = ∑ j=1 i-1 c ij x j (k+1) + ∑ n j=i c ij x j (k) + d i , i = 1, ..., n | (1.20) |
Условието за края на итеративния процес на Seidel при постигане на точността ε в опростен вид има формата:
|| x (k+1) - x (k) || ≤ ε.
Билет №30
Метод на преминаване
За решаване на системи A x = b с тридиагонална матрица най-често се използва методът на почистване, който е адаптация на метода на Гаус за този случай.
Нека напишем системата от уравнения
d 1 x 1 + e 1 x 2 = b 1
c 2 x 1 + d 2 x 2 + e 2 x 3 = b 2
c 3 x 2 + d 3 x 3 + e 3 x 4 = b 3
... ... ...
c n-1 x n-2 + d n-1 x n-1 + e n-1 x n = b n-1
c n x n-1 + d n x n = b n
в матрична форма: A x = b където
А= 
Нека запишем формулите на метода на почистване в реда на тяхното приложение.
1. Директен ход на метода на почистване (изчисляване на спомагателни количества):
| a 2 = -e 1 / d 1 b 2 = b 1 / d 1 a i+1 = -e i / , i=2, ..., n-1 b i+1 = [-c i b i + b i ] / , i=2, ..., n-1 | (1.9) |
2. Обратен ходметод на почистване (намиране на решение):
| x n = [-c n b n + b n ] / x i = a i+1 x i+1 + b i+1, i = n-1, ..., 1 |
Билет №31
Метод на проста итерация
Същността на метода прости итерациисе състои в преминаване от уравнението
f(x)= 0 (*)
към еквивалентното уравнение
х=φ(x). (**)
Този преход може да се направи различни начини, в зависимост от вида f(x). Например, можете да поставите
φ(x) = х+bf(x),(***)
Където b= const и корените оригинално уравнениеняма да се промени.
Ако е известно първоначалното приближение до корена х 0, след това новото приближение
х 1=φx(0),
тези. обща схема на итеративния процес:
x k+1=φ(x k).(****)
Най-простият критерий за приключване на процеса
|x k +1 -x k |<ε.
Критерий за конвергенцияметод на проста итерация:
ако е близо до корена | φ/(x)| < 1, то итерации сходятся. Если указанное условие справедливо для любого х, тогава итерациите се събират за всяко първоначално приближение.
Нека проучим избора на константа bот гледна точка на осигуряване на максимална скорост на конвергенция. В съответствие с критерия за конвергенция най-високата скорост на конвергенция се осигурява, когато |φ / (x)| = 0. В същото време, въз основа на (***), b = –1/f / (x),и формулата за итерация (****) влиза в x i =x i-1 -f(x i-1)/f/ (x i-1).-тези. във формулата на метода на Нютон. По този начин методът на Нютон е специален случай на метода на простата итерация, осигуряващ най-високата скорост на сближаване на всички възможни опции за избор на функция φ(x).
Билет №32
Метод на Нютон
Основната идея на метода е следната: в близост до хипотетичния корен се задава първоначално приближение, след което в точката на приближаване се конструира допирателна към изследваната функция, за която се намира пресечната точка с абсцисната ос. Тази точка се приема като следващо приближение. И така до постигане на необходимата точност.
Нека е функция с реална стойност, дефинирана на интервал и диференцируема на него. Тогава формулата за итеративно апроксимационно смятане може да бъде получена, както следва:
където α е ъгълът на наклона на допирателната в точката.
Следователно търсеният израз за има формата:
Билет №33
Метод на златното сечение
Методът на златното сечение ви позволява да елиминирате интервали, като изчислявате само една функционална стойност при всяка итерация. В резултат на двете разглеждани стойности на функцията се определя интервалът, който трябва да се използва в бъдеще. Този интервал ще съдържа една от предишните точки и следващата точка, поставена симетрично спрямо нея. Точката разделя интервала на две части, така че отношението на цялото към по-голямата част е равно на отношението на по-голямата част към по-малката, т.е. равно на така нареченото „златно сечение“.
Разделянето на интервала на неравни части ви позволява да намерите още по-ефективен метод. Нека изчислим функцията в краищата на сегмента [ а,b] и поставете а=х 1 , b=х 2. Нека изчислим функцията и в две вътрешни точки х 3 , х 4 . Нека сравним всичките четири стойности на функцията и да изберем най-малката сред тях. Нека например да се окаже най-малкият f(х 3). Очевидно минимумът трябва да е в един от сегментите, съседни на него. Следователно сегментът [ х 4 ,b] могат да бъдат отхвърлени и да напуснат сегмента. 
Първата стъпка е направена. На сегмента отново трябва да изберете две вътрешни точки, да изчислите стойностите на функцията в тях и в краищата и да предприемете следващата стъпка. Но в предишната стъпка от изчисленията вече намерихме функцията в краищата на новия сегмент и в една от вътрешните му точки х 4 . Следователно е достатъчно да изберете още една точка вътре х 5определи стойността на функцията в него и направи необходимите сравнения. Това учетворява обема на изчисленията, необходими за стъпка на процеса. Кой е най-добрият начин за поставяне на точки? Всеки път оставащият сегмент се разделя на три части и след това един от външните сегменти се изхвърля.
Нека означим началния интервал на неопределеност с д.
Тъй като в общия случай всеки от сегментите може да бъде изхвърлен X 1, X 3или X 4, X 2след това изберете точките X 3И X 4така че дължините на тези сегменти да са еднакви:
x 3 -x 1 =x 4 -x 2.
След изхвърляне получаваме нов интервал на несигурност на дължината Д'.
Нека обозначим отношението д/Д'буква φ:
тоест, нека зададем къде е следващият интервал на несигурност. Но
равна по дължина на сегмента, изхвърлен на предишния етап, т.е
Следователно получаваме:
.
Това води до уравнението или, еквивалентно 
.
Положителният корен на това уравнение дава
.
Билет №34
интерполация на функции, т.е. Използване на дадена функция, конструиране на друга (обикновено по-проста) функция, чиито стойности съвпадат със стойностите на дадената функция в определен брой точки. Освен това интерполацията има както практическо, така и теоретично значение.
Методът на простата итерация, наричан още метод на последователно приближение, е математически алгоритъм за намиране на стойността на неизвестно количество чрез постепенното му прецизиране. Същността на този метод е, че както подсказва името, постепенно изразявайки следващите от първоначалното приближение, се получават все по-прецизни резултати. Този метод се използва за намиране на стойността на променлива в дадена функция, както и при решаване на системи от уравнения, както линейни, така и нелинейни.
Нека разгледаме как този метод се прилага при решаване на SLAE. Методът на проста итерация има следния алгоритъм:
1. Проверка на изпълнението на условието за сходимост в изходната матрица. Теорема за конвергенция: ако оригиналната матрица на системата има диагонална доминация (т.е. във всеки ред елементите на главния диагонал трябва да са по-големи по абсолютна стойност от сумата на елементите на второстепенните диагонали по абсолютна стойност), тогава простата итерационният метод е конвергентен.
2. Матрицата на оригиналната система не винаги има диагонален превес. В такива случаи системата може да бъде преобразувана. Уравненията, които отговарят на условието за конвергенция, се оставят недокоснати и се правят линейни комбинации с тези, които не отговарят, т.е. умножение, изваждане, добавяне на уравнения едно към друго, докато се получи желаният резултат.
Ако в получената система има неудобни коефициенти на главния диагонал, тогава членовете на формата с i * x i се добавят към двете страни на такова уравнение, чиито знаци трябва да съвпадат със знаците на диагоналните елементи.
3. Преобразуване на получената система в нормална форма:
x - =β - +α*x -
Това може да стане по много начини, например по следния начин: от първото уравнение изразете x 1 чрез други неизвестни, от второто - x 2, от третото - x 3 и т.н. В този случай използваме формулите:
α ij = -(a ij / a ii)
i = b i /a ii
Отново трябва да се уверите, че получената система с нормална форма отговаря на условието за конвергенция:
∑ (j=1) |α ij |≤ 1, докато i= 1,2,...n
4. Започваме да прилагаме всъщност самия метод на последователните приближения.
x (0) е първоначалното приближение, ще изразим x (1) чрез него, след това ще изразим x (2) чрез x (1). Общата формула в матрична форма изглежда така:
x (n) = β - +α*x (n-1)
Изчисляваме, докато постигнем необходимата точност:
max |x i (k)-x i (k+1) ≤ ε
И така, нека приложим простия итерационен метод на практика. Пример:
Решете SLAE:
4.5x1-1.7x2+3.5x3=2
3.1x1+2.3x2-1.1x3=1
1.8x1+2.5x2+4.7x3=4 с точност ε=10 -3
Да видим дали диагоналните елементи преобладават в модула.
Виждаме, че само третото уравнение удовлетворява условието за конвергенция. Преобразуваме първото и второто и добавяме второто към първото уравнение:
7,6x1+0,6x2+2,4x3=3
От третия изваждаме първия:
2,7x1+4,2x2+1,2x3=2
Преобразувахме оригиналната система в еквивалентна:
7,6x1+0,6x2+2,4x3=3
-2,7x1+4,2x2+1,2x3=2
1.8x1+2.5x2+4.7x3=4
Сега нека приведем системата в нормалната й форма:
x1=0,3947-0,0789x2-0,3158x3
x2=0,4762+0,6429x1-0,2857x3
x3= 0,8511-0,383x1-0,5319x2
Проверяваме сходимостта на итеративния процес:
0.0789+0.3158=0,3947 ≤ 1
0.6429+0.2857=0.9286 ≤ 1
0,383+ 0,5319= 0,9149 ≤ 1, т.е. условието е изпълнено.
0,3947
Първоначално предположение x(0) = 0,4762
0,8511
Замествайки тези стойности в уравнението на нормалната форма, получаваме следните стойности:
0,08835
x(1) = 0,486793
0,446639
Заменяйки нови стойности, получаваме:
0,215243
x(2) = 0,405396
0,558336
Продължаваме изчисленията, докато се доближим до стойности, които отговарят на даденото условие.
х (7) = 0,441091
Нека проверим правилността на получените резултати:
4,5*0,1880 -1.7*0,441+3.5*0,544=2,0003
3,1*0,1880+2,3*0,441-1,1x*0,544=0,9987
1.8*0,1880+2.5*0,441+4.7*0,544=3,9977
Резултатите, получени чрез заместване на намерените стойности в оригиналните уравнения, напълно отговарят на условията на уравнението.
Както виждаме, простият итерационен метод дава доста точни резултати, но за да решим това уравнение, трябваше да отделим много време и да направим тромави изчисления.
Нека е дадена система от n алгебрични уравнения с n неизвестни:
Алгоритъм за метода на проста итерация:
Забележете, че тук и занапред долният индекс обозначава съответния компонент на вектора на неизвестните, а горният индекс номерът на итерация (апроксимация).
След това се формира цикличен математически процес, всеки цикъл от който представлява една итерация. В резултат на всяка итерация се получава нова стойност на вектора на неизвестните. За да организираме итеративния процес, записваме система (1) в намалена форма. В този случай членовете на главния диагонал се нормализират и остават вляво от знака за равенство, а останалите се прехвърлят в дясната страна. Редуцирана система от уравненияима формата:
забележи това никога няма да бъде постигнато, но с всяка следваща итерация векторът на неизвестните се доближава до точното решение.
12. Основната итерационна формула, използвана в простия итерационен метод за решаване на нелинейно уравнение:
13. Критерий за спиране на итеративния процес при простия итерационен метод за решаване на нелинейно уравнение:
Итеративният процес приключва, ако за всеки i-ти компонент на вектора на неизвестните е изпълнено условието за постигане на точност.
забележи това точно решение в метода на простата итерацияникога няма да бъде постигнато, но с всяка следваща итерация векторът на неизвестните се доближава все повече и повече до точното решение
14. Критерий за избор на спомагателна функция F(x) за итеративния сегмент от интервала:
При полагане на тест по математика за решаване на простия итерационен метод първо трябва да се провери условието за сходимост. За да се сближи методът, е необходимо и достатъчно в матрица А абсолютните стойности на всички диагонални елементи да са по-големи от сумата на модулите на всички други елементи в съответния ред:
Недостатък на итеративните методиТова е доста строго условие за сходимост, което не е изпълнено за всички системи уравнения.
Ако условието за конвергенция е изпълнено, тогава на следващия етап е необходимо да се посочи първоначално приближение на вектора на неизвестните, който обикновено се избира като нулев вектор:
15. Методът на Гаус, използван за решаване на системи от линейни уравнения, осигурява:
Методът се основава на преобразуване на матрица в триъгълна форма. Това се постига чрез последователно елиминиране на неизвестни от уравненията на системата.
Методът на проста итерация се основава на замяна на оригиналното уравнение с еквивалентно уравнение:
Нека първоначалното приближение до корена е известно x = x 0. Замествайки го в дясната страна на уравнение (2.7), получаваме ново приближение 
, тогава по подобен начин получаваме 
и др.:
. (2.8)
 |
Не при всички условия итеративният процес се свежда до корена на уравнението х. Нека разгледаме по-подробно този процес. Фигура 2.6 показва графична интерпретация на еднопосочен конвергентен и дивергентен процес. Фигура 2.7 показва двупосочни конвергентни и дивергентни процеси. Дивергентният процес се характеризира с бързо нарастване на стойностите на аргумента и функцията и необичайно прекратяване на съответната програма.
 |
При двупосочен процес е възможно циклизиране, тоест безкрайно повторение на една и съща функция и стойности на аргумент. Цикълът разделя дивергентния процес от конвергентния.
От графиките става ясно, че както за едностранните, така и за двустранните процеси конвергенцията към корена се определя от наклона на кривата близо до корена. Колкото по-малък е наклонът, толкова по-добра е конвергенцията. Както е известно, тангенсът на наклона на кривата е равен на производната на кривата в дадена точка.
Следователно, колкото по-малко е числото близо до корена, толкова по-бързо се сближава процесът.
За да бъде итерационният процес конвергентен, трябва да е изпълнено следното неравенство в близост до корена:
Преходът от уравнение (2.1) към уравнение (2.7) може да се извърши по различни начини в зависимост от вида на функцията f(x).При такъв преход е необходимо да се конструира функцията така, че да е изпълнено условието за сходимост (2.9).
Нека разгледаме един от общите алгоритми за преход от уравнение (2.1) към уравнение (2.7).
Нека умножим лявата и дясната страна на уравнение (2.1) по произволна константа bи добавете неизвестното към двете части Х.В този случай корените на оригиналното уравнение няма да се променят:
Нека въведем нотацията 
и нека преминем от отношение (2.10) към уравнение (2.8).
 |
Произволен избор на константа bще осигури изпълнението на условието за конвергенция (2.9). Критерият за завършване на итеративния процес ще бъде условие (2.2). Фигура 2.8 показва графична интерпретация на метода на простите итерации, използвайки описания метод на представяне (мащабите по осите X и Y са различни).
Ако функция е избрана във формата , тогава производната на тази функция ще бъде . Тогава най-високата скорост на конвергенция ще бъде при 
и итерационната формула (2.11) влиза във формулата на Нютон. По този начин методът на Нютон има най-висока степен на сходимост от всички итеративни процеси.
Софтуерната реализация на простия итерационен метод е направена под формата на подпрограма Итерас(ПРОГРАМА 2.1).
Цялата процедура на практика се състои от един цикъл Repeat ... Until, прилагащ формула (2.11), като се вземе предвид условието за спиране на итеративния процес (формула (2.2)).
Процедурата има вградена защита на цикъла чрез преброяване на броя на циклите с помощта на променливата Niter. В практическите занятия трябва да се уверите, като стартирате програмата, как се отразява изборът на коефициент bи първоначално приближение в процеса на търсене на корена. При промяна на коеф bестеството на итерационния процес за изследваната функция се променя. Първо се превръща в двустранна, а след това в цикли (фиг. 2.9). Осови везни хИ Yса различни. Още по-висока стойност на модул b води до различен процес.
Сравнение на методи за приближено решаване на уравнения
Сравнението на описаните по-горе методи за числено решение на уравнения беше извършено с помощта на програма, която ви позволява да наблюдавате процеса на намиране на корена в графична форма на екрана на компютъра. Процедурите, включени в тази програма и прилагащи сравняваните методи, са дадени по-долу (ПРОГРАМА 2.1).
Ориз. 2.3-2.5, 2.8, 2.9 са копия на компютърния екран в края на процеса на итерация.
Във всички случаи квадратното уравнение x 2 -x-6 = 0 беше взето като изследвана функция, имаща аналитично решение x 1 = -2 и x 2 = 3. Грешката и първоначалните приближения бяха приети еднакви за всички методи. Резултати от коренно търсене x= 3, представени на фигурите, са както следва. Най-бавно се сближава методът на дихотомията - 22 итерации, най-бърз е методът на простата итерация с b = -0,2 - 5 итерации. Тук няма противоречие с твърдението, че методът на Нютон е най-бързият.
Производна на изследваната функция в точката х= 3 е равно на -0,2, т.е. изчислението в този случай е извършено практически по метода на Нютон със стойността на производната в точката на корена на уравнението. При промяна на коеф bскоростта на сближаване спада и процесът на постепенно сближаване първо преминава в цикли и след това става дивергентен.
По аналогия с (2.1) системата (5.1) може да бъде представена в следния еквивалентен вид:
където g(x) е итеративна векторна функция на векторния аргумент. Системите от нелинейни уравнения често възникват директно във формата (5.2) (например в числените схеми за диференциални уравнения в този случай не са необходими допълнителни усилия за трансформиране на уравнения (5.1) в система (5.2). Ако продължим аналогията с простия итерационен метод за едно уравнение, тогава итерационният процес, базиран на уравнение (5.2), може да бъде организиран, както следва:
- 1) някакъв начален вектор x ((,) e 5 o (x 0, а)(приема се, че x* e 5„(x 0, А));
- 2) последващите приближения се изчисляват по формулата
тогава процесът на итерация е завършен и
Както и преди, трябва да разберем при какви условия
Нека обсъдим този въпрос, като извършим прост анализ. Първо въвеждаме грешката на i-то приближение като e(^ = x(i) - x*. След това можем да запишем
Нека заместим тези изрази в (5.3) и разширим g(x* + e (/i)) по степени e(k>в близост до x* като функция на векторния аргумент (приемайки, че всички частни производни на функцията g(x) са непрекъснати). Като вземем предвид също, че x* = g(x*), получаваме
или в матрична форма
B = (bnm)= I (x*)1 - итерационна матрица.
Ако процентът на грешки ||е®|| е достатъчно малък, тогава вторият член от дясната страна на израз (5.4) може да бъде пренебрегнат и тогава той съвпада с израз (2.16). Следователно условието за сходимост на итеративния процес (5.3) близо до точното решение е описано от теорема 3.1.
Конвергенция на метода на простата итерация. Необходими и достатъчно условиеза конвергенцията на итеративния процес (5.3): 
и достатъчно условие:
Тези условия имат по-скоро теоретично, отколкото практическо значение, тъй като не знаем x'. По аналогия с (1.11) получаваме условие, което може да бъде полезно. Нека x* e 5 o (x 0, а)и матрицата на Якоби за функцията g(x)
съществува за всички x e S n (x 0 , a) (обърнете внимание, че C(x*) = B). Ако елементите на матрицата C(x) удовлетворяват неравенството
за всички x e 5„(x 0, А),тогава достатъчното условие (5.5) също е изпълнено за всяка матрична норма.
Пример 5.1 (метод на проста итерация) Помислете следната системауравнения:
Една възможност за представяне на тази система в еквивалентна форма (5.2) е да се изрази хот първото уравнение и х 2от второто уравнение: 
Тогава итерационната схема има формата
Точното решение е x* e 5„((2, 2), 1). Нека изберем началния вектор x (0) = (2,2) и ? p = CT 5. Резултатите от изчислението са представени в табл. 5.1.
Таблица 5.1
|
||X - X (i_1 > | 2 / X (A) 2 |
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
Тези резултати показват, че конвергенцията е доста бавна. За да получим количествена характеристика на конвергенцията, извършваме прост анализ, като считаме x (1/) за точно решение. Матрицата на Якоби C(x) за нашата итеративна функция има формата
тогава матрица B се оценява приблизително като
Лесно е да се провери, че нито условие (5.5), нито условие (5.6) са изпълнени, но има конвергенция, тъй като 5(B) ~ 0.8.
Често е възможно да се ускори конвергенцията на простия итерационен метод чрез лека промяна на процеса на изчисление. Идеята на тази модификация е много проста: да се изчисли Пкомпоненти на вектора x (A+1)може да се използва не само (t = n,..., н), но също и вече изчислените компоненти на следващия апроксимационен вектор x k^ (/= 1,P - 1). По този начин модифицираният метод на проста итерация може да бъде представен като следната итерационна схема:
Ако приближенията, генерирани от итеративния процес (5.3), се сближават, тогава итеративният процес (5.8) има тенденция да се сближава по-бързо поради по-пълното използване на информацията.
Пример 5.2 (модифициран метод на проста итерация) Модифицираната проста итерация за система (5.7) е представена като
Както преди, избираме началния вектор x (0) = (2, 2) и g r = = 10 -5. Резултатите от изчислението са представени в табл. 5.2.
Таблица 5.2
|
|||
|
|||
|
|||
|
I Голямата промяна в реда на изчисленията доведе до намаляване наполовина на броя на повторенията и следователно наполовина на броя на операциите.
