Прост итерационен метод с оптимален параметър. Итеративни методи за решаване на блатото

Методът на проста итерация, наричан още метод последователно приближение, - това е математически алгоритъмнамиране на стойността на неизвестно количество чрез постепенното му прецизиране. Същността на този метод е, че, както подсказва името, постепенно изразявайки следващите от първоначалното приближение, те получават все по-прецизни резултати. Този метод се използва за намиране на стойността на променлива в дадена функция, както и при решаване на системи от уравнения, както линейни, така и нелинейни.

Помислете как този методсе реализира при решаване на SLAE. Методът на проста итерация има следния алгоритъм:

1. Проверка на условието за сходимост в оригиналната матрица. Теорема за конвергенция: ако първоначалната матрица на системата има диагонална доминация (т.е. във всеки ред елементите на главния диагонал трябва да са по-големи по модул от сумата на елементите на второстепенните диагонали по модул), тогава методът прости итерации- сближаване.

2. Матрицата на оригиналната система не винаги има диагонална доминация. В такива случаи системата може да бъде модифицирана. Уравненията, които отговарят на условието за конвергенция, остават незасегнати, а с тези, които не отговарят, те образуват линейни комбинации, т.е. умножение, изваждане, добавяне на уравнения едно към друго, докато се получи желаният резултат.

Ако в получената система има неудобни коефициенти на главния диагонал, тогава членовете на формата c 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 (1) изразяваме x (2) . Обща формулаа матрична формаизглежда така:

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

Продължаваме изчисленията, докато се доближим до стойностите, които отговарят на даденото условие.

x(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

Резултатите, получени чрез заместване на намерените стойности в оригиналните уравнения, напълно отговарят на условията на уравнението.

Както виждаме, простият итерационен метод дава доста точни резултати, но за да решим това уравнение, трябваше да отделим много време и да направим тромави изчисления.

Обмисли линеен алгебрични уравнения

Да похарчим няколко еквивалентни трансформации. Умножаваме двете части на системата по един и същ скаларен коефициент, след което добавяме вектор към дясната и лявата част на системата.Системата от уравнения вече може да бъде записана във форма, удобна за повторения:

(2.15)

Сега нека изградим последователност от приближения към решението на системата. Избираме произволен вектор - първоначалното приближение на решението. Най-често просто се приема, че е нулев вектор. Най-вероятно първоначалното приближение не удовлетворява (2.15) и, следователно, оригиналната система. Когато се замести в оригиналното уравнение, възниква несъответствие. Изчислявайки несъответствието, използвайки (2.15), можем да прецизираме приближението към решението, като приемем, че

Според първото приближение несъответствието се изчислява отново, процесът продължава. В хода на итерацията получаваме еквивалентна формулировка на метода, наречен метод на проста итерация, е както следва. Решение (2.15) се намира като граница на редицата апроксимации, чиито членове са свързани с рекурсивна връзка (тя е еквивалентна на дадената по-горе, остатъчният вектор е изключен от нотацията):

(2.16)

(или всяка произволен вектор). Ако границата на такава последователност съществува, тогава се говори за конвергенцияитеративен процес към решението на SLAE.

Има и други форми на писане на итерационния метод, като напр

За последната формула съответства на еднопараметърния итеративен процес, обсъден по-горе метод на проста итерация. За , - n-стъпков изричен итеративен процес, за , - метод на проста итерациябез параметър за итерация. В случай, когато, итеративен методНаречен имплицитно- за изчисление следващо приближениеЗа да го решите, ще трябва да решите система от линейни уравнения (обикновено по-проста от оригиналната).

теорема ( достатъчно условиеконвергенция метод на проста итерация). Итеративният процес (2.16) се свежда до решението на SLAE със скорост геометрична прогресиякогато е изпълнено условието:

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

Нека е точното решение на система (2). Изваждайки от (2.16)-(2.15), получаваме , или, обозначавайки грешката , получаваме уравнението за еволюцията на грешката Валидна е веригата от неравенства: , където

От това следва, че когато

От неравенството може да се получи оценка на броя итерации, необходими за постигане на точност, т.е. да отговаря на условието Тази оценка има формата

Теорема (критерий за сходимост метод на проста итерация (няма доказателство)). Нека SLAE (2.15) има уникално решение. Тогава за конвергенцията на итеративния процес (2.16) е необходимо и достатъчно всички собствени стойностиматрици от абсолютна стойностбяха по-малко от един.

Сравнете по количество аритметични операциидиректен и итеративни методи. Методът на Гаус без избор на главния елемент изисква

Аритметични операции; метод на проста итерация (2.16) , където i е броят на приближенията, необходими за постигане на дадената точност. И така, за мен< n/3 метод итераций становится предпочтительнее. В реални задачи, основно, в допълнение, итеративни методимогат да бъдат направени по-ефективни чрез промяна на параметрите на итерацията. В някои случаи итеративни методисе оказват по-стабилни по отношение на натрупването на грешки при закръгляване от правите линии.

Лекция Итеративни методи за решаване на система от алгебрични линейни уравнения.

Условие за сходимост на итеративния процес Метод на Якоби Метод на Зайдел

Метод на проста итерация

Разглежда се системата от линейни алгебрични уравнения

За да се приложат итеративни методи, системата трябва да бъде редуцирана до еквивалентна форма

След това се избира първоначалното приближение към решението на системата от уравнения и се намира последователност от приближения към корена.

За да се сближи итеративният процес, е достатъчно условието
(матрична норма). Критерият за прекратяване на итерациите зависи от приложения итеративен метод.

Метод на Якоби .

Най-простият начин да доведете системата до форма, удобна за итерация, е както следва:

От първото уравнение на системата изразяваме неизвестното х 1 , от второто уравнение на системата изразяваме х 2 и т.н.

В резултат на това получаваме система от уравнения с матрица B, в която нула елементи са на главния диагонал, а останалите елементи се изчисляват по формулите:

Компонентите на вектора d се изчисляват по формулите:

Формулата за изчисление на простия итерационен метод е:

или в координатна нотация изглежда така:

Критерият за прекратяване на итерациите в метода на Якоби има формата:

Ако
, тогава може да се приложи по-прост критерий за прекратяване на итерациите

Пример 1Решение на система от линейни уравнения по метода на Якоби.

Нека е дадена системата от уравнения:

Изисква се да се намери решение на системата с точност

Привеждаме системата във форма, удобна за итерация:

Избираме първоначално приближение, например

е векторът на дясната страна.

Тогава първата итерация изглежда така:

Следните приближения към решението се получават по подобен начин.

Намерете нормата на матрицата B.

Ще използваме нормата

Тъй като сумата от модулите на елементите във всеки ред е 0,2, тогава
, така че критерият за прекратяване на итерациите в този проблем е

Нека изчислим нормите на разликите на векторите:

защото
определената точност се достига при четвъртата итерация.

Отговор: х 1 = 1.102, х 2 = 0.991, х 3 = 1.0 1 1

Метод на Seidel .

Методът може да се разглежда като модификация на метода на Якоби. Основната идея е, че при изчисляване на следващия (n+1)-то приближение до неизвестното х азпри i>1употреба вече е намерена (n+1)-приближава непознатото х 1 ,х 2 , ...,х i - 1, не нто приближение, както в метода на Якоби.

Формулата за изчисление на метода в координатно обозначение изглежда така:

Условията за конвергенция и критерият за прекратяване на итерациите могат да се приемат същите като в метода на Якоби.

Пример 2Решаване на системи от линейни уравнения по метода на Зайдел.

Разгледайте успоредно решението на 3 системи от уравнения:

Привеждаме системите във вид, удобен за итерации:

Обърнете внимание, че условието за конвергенция
извършва се само за първата система. Изчисляваме 3 първи приближения към решението във всеки случай.

1-ва система:

Точното решение ще бъдат стойностите: х 1 = 1.4, х 2 = 0.2 . Итеративният процес се сближава.

2-ра система:

Може да се види, че итеративният процес се разминава.

Точно решение х 1 = 1, х 2 = 0.2 .

3-та система:

Може да се види, че итеративният процес е зациклил.

Точно решение х 1 = 1, х 2 = 2 .

Нека матрицата на системата от уравнения A е симетрична и положително определена. След това, за всеки избор на първоначалното приближение, методът на Seidel се сближава. Тук не се налагат допълнителни условия за малкостта на нормата на дадена матрица.

Метод на проста итерация.

Ако A е симетрична и положително определена матрица, тогава системата от уравнения често се свежда до еквивалентна форма:

х=х-τ(A х- b), τ е итеративен параметър.

Формулата за изчисляване на простия итерационен метод в този случай е:

х (n+1) =х н- τ (А х (н) - б).

и параметърът τ > 0 е избран така, че ако е възможно, минималната стойност

Нека λ min и λ max са минималните и максималните собствени стойности на матрицата A. Оптималният избор е параметърът

В такъв случай
приема минимална стойностравна на:

Пример 3 Решаване на системи от линейни уравнения чрез проста итерация. (в MathCAD)

Нека системата от уравнения Ax = b

Да се ​​изгради итеративен процес намерим нашите собственичисла на матрица А:

- използва вградена функция за намиране на собствени стойности.

Изчислете итеративния параметър и проверете условието за сходимост

Условието за конвергенция е изпълнено.

Нека вземем първоначалното приближение - вектора x0, зададем точността на 0,001 и намерим първоначалните приближения с помощта на програмата по-долу:

Точно решение

Коментирайте. Ако програмата върне матрицата rez, тогава можете да видите всички намерени итерации.

1. Нека е известна отсечка, която съдържа един корен на уравнението f(x) = 0. Функцията f е непрекъснато диференцируема функция на тази отсечка (f(x)нC 1 ). Ако тези условия са изпълнени, може да се използва методът на проста итерация.

2. Въз основа на функцията f(x) се конструира функция j(x), която отговаря на три условия: тя трябва да бъде непрекъснато диференцируема (j(x)нC 1 ), така че уравнението x = j(x) е еквивалентно на уравнението f(x)=0; трябва също превод на сегмент в себе си.

Ще кажем, че функцията j (х ) превежда сегмента [а , b ] в себе си, ако имах Î [ а , b ], г = й (х ) също принадлежи[ а , b ] (г Î [ а , b ]).

Третото условие е наложено на функцията j(x):

Формула на метода: x n +1 = j(xn).

3. Когато тези три условия са изпълнени, за всяко първоначално приближение x 0 n последователност от итерации x n +1 = j(x n) се сближава към корена на уравнението: x = j(x) на сегмента ().

Като правило, като x 0 един от краищата е избран.

,

където e е определената точност

Число x n +1 при условие на спиране на итеративния процес е приблизителна стойност на корена на уравнението f(x) = 0 на сегмента, намира се по метода на простата итерация с точностд .

Изградете алгоритъм за прецизиране на корена на уравнението: x 3 + 5x - 1 = 0 върху сегмента чрез проста итерация с точност e .

1. Функция f(x) = x 3 +5x-1 е непрекъснато диференцируем на сегмент, съдържащ един корен на уравнение.

2. Най-голямата трудност при простия итерационен метод е конструирането на функция j(x), която да отговаря на всички условия:

Обмисли: .

Уравнение x = j 1 (x) е еквивалентно на уравнението f(x) = 0, но функцията j 1 (x) не е непрекъснато диференцируема на интервала .

Ориз. 2.4. Графика на функция j 2 (x)

От друга страна, следователно,. Следователно: е непрекъснато диференцируема функция. Обърнете внимание, че уравнението: x = j 2 (x) е еквивалентно на уравнението f(x) = 0 . От графиката (фиг. 2.4) се вижда, че функцията j 2 (x) транслира сегмента в себе си.

Условието, че функцията j(x) трансформира сегмента в себе си, може да бъде преформулирано по следния начин: нека е домейнът на функцията j(x) и е домейнът на j(x).

Ако сегментът принадлежи на сегмента , тогава функцията j(x) взема сегмента в себе си.

, .

Всички условия за функцията j(x) са изпълнени.

Формула на итеративния процес: x n +1 = й 2(xn).

3. Първоначално приближение: x 0 = 0.

4. Условие за спиране на итеративния процес:

Ориз. 2.5. геометричен смисълметод на проста итерация

.

Когато това условие е изпълнено, x n +1 – приблизителната стойност на корена върху сегмента, намира се чрез проста итерация с точност д. На фиг. 2.5. илюстрирано е приложението на метода на простата итерация.

Теорема за сходимост и оценка на грешката

Нека сегментът съдържа един корен на уравнението x = j(x), функция j(x ) е непрекъснато диференцируем на сегмента , превежда сегмента в себе си и състоянието:

.

След това за всяко първоначално приближение х 0 О подпоследователност се сближава към корена на уравнението г = j(x ) на сегмента и оценката на грешката:

.

Стабилност на метода на простата итерация. При условията на теоремата за сходимост алгоритъмът на метода на простата итерация е стабилен.

Сложността на простия итерационен метод. Количеството компютърна памет, необходимо за прилагане на метода на проста итерация, е незначително. На всяка стъпка трябва да съхранявате x n , x n +1 , р и д.

Нека оценим броя на аритметичните операции, необходими за прилагане на простия итерационен метод. Нека напишем оценка за числото n 0 = n 0 (e), така че за всички n ³ n 0 да е валидно следното неравенство:

От тази оценка следва, че колкото по-близо е q до единица, толкова по-бавно се сближава методът.

Коментирайте. Не съществува общо правилоконструиране на j(x) от f(x) по такъв начин, че да са изпълнени всички условия на теоремата за конвергенция. Често се използва следният подход: функцията j се избира като функция j(x) = x + k × f(x), където k – постоянен.

Когато програмирате прост итерационен метод, спирането на итеративен процес често изисква две условия да бъдат изпълнени едновременно:

и .

Всички други итеративни методи, които ще разгледаме, са специални случаи на простия итерационен метод. Например, когато Методът на Нютон е специален случай на метода на простата итерация.

В този раздел разглеждаме стационарен итерационен процес, когато матрицата и итерационният параметър не зависят от индекса , и докажете следната теорема за достатъчни условия за нейната сходимост.

Теорема на Самарски

Позволявам е самосвързана положително определена матрица:

,
,

е положително определена матрица, - положително число:

,
.

Тогава за всеки избор на нулево приближение итеративен процес, който се дефинира от рекурсивната формула , се сближава с решението на оригиналната система.

Преди да преминем към доказателството на теоремата, нека обсъдим по-подробно нейното основно изискване, положителната определеност на матрицата
. Това изискване може да бъде пренаписано като:

,
,
.

т.е. по-специално се приема, че матрицата е положително определено. Освен това неравенството определя интервала, в който параметърът може да се промени :

.

След тези забележки преминаваме към доказателството на теоремата. Нека изразим от отношението през :

и заменете в рекурентната формула за итеративната последователност. В резултат на това получаваме:

.

Разликата между итеративната формула и е, че е хомогенна.

Матрица е положително определено. Следователно, той е неизроден и има обратен
. С нейна помощ рекурентна връзкаможе да бъде разрешено относно
:

, така
.

Умножение на двете страни на равенството отляво по матрицата , получаваме още една рекурентна връзка

.

Помислете за последователността от положителни функционали:

.

Нека съставим подобен израз за
и го трансформирайте с помощта на повтарящи се формули и:

От самосвързаността на матрицата и формулите следват

В резултат на това формулата приема формата:

По този начин последователността от функционали при спазване на условието
образува монотонно ненарастваща редица, ограничена отдолу с нула

.

,

където
е строго положителна константа. В резултат на това според и ще имаме

От това неравенство и сходимостта на последователността от функционали следва това
при
. На свой ред
, така

Теоремата е доказана.

1. Метод на проста итерация.

Това име е дадено на метода, при който като матрица матрицата на идентичност е избрана:
и итеративния параметър се приема, че не зависи от номера на итерацията . С други думи, методът на проста итерация е изричен стационарен метод при следващата итерация
се изчислява по рекурсивната формула

Ще приемем, че матрицата удовлетворява условието на теоремата на Самарски,
, тогава формулата, която определя границата на интервала на конвергенция по отношение на итеративния параметър , приема формата

.

Позволявам
- ортонормална база на собствените вектори на оператора, съответстващ на матрицата . Чрез положителна определеност всички негови собствени стойности са положителни. Нека ги разгледаме номерирани в низходящ ред:

Нека разложим вектора
според основата на собствените вектори

В резултат на това от формулата следва, че методът на проста итерация се сближава за всеки принадлежащ на интервала

.

Ще изградим по-нататъшно изследване на простия итерационен метод върху специфичен анализ на рекурсивната формула. Нека въведем матрицата на оператора на прехода

,

и пренапишете формулата като

.

В същото време грешката
ще отговаря на подобна рекурентна връзка, само че хомогенна

.

Нека докажем две леми, които ни позволяват да изследваме по-пълно условията за сходимост на метода на простата итерация.

Лема 1

Нека операторът, който генерира матрицата , има собствен вектор със собствена стойност , след това операторът на преход, генериран от матрицата , също има собствен вектор , но със собствена стойност

.

Доказателството е елементарно. Извършва се чрез директна проверка

За самосвързана матрица матрица също е самосвързан. Следователно неговата норма се определя от най-голямата собствена стойност по абсолютна стойност
:

.

Лема 2

За да може простият итерационен метод да се сближи с решението на системата за всеки избор на първоначално приближение, е необходимо и достатъчно всички собствени стойности на оператора на прехода бяха по модул по-малки от едно:

,

Адекватност. Условието означава, че нормата на матрицата , според, ще бъде по-малко от единица:
. В резултат на това получаваме

При
.

Трябва. Нека приемем, че сред собствените стойности намери поне един , което не отговаря на условието на лемата, т.е.

.

Нека изберем нулевия член на итеративната последователност във формата
, където решение на системата, тогава нулевият член на последователността на грешките ще съвпадне със собствения вектор скок оператор :
. Като резултат повтаряща се формулаза следните членове на последователността от грешки ще приеме формата:

,
.

т.е.
. Необходимостта от изпълнение на неравенството за всички собствени стойности за сходимостта на метода на простата итерация е доказана.

Лема 2 дефинира програмата за по-нататъшно изследване на конвергенцията на метода на простата итерация: необходимо е да се зададе диапазонът на вариация на параметъра при които всички собствени стойности удовлетворяват неравенството. Лесно е да се направи. На фиг. 1 показва графики на намаляване линейни функции
. Всички те идват от една и съща точка
,
и намаляват поради отрицателни коефициенти при , и най-бързо намаляващата функция
. Когато придобие смисъл
, условието за него престава да се изпълнява:

, при
.

Намерена стойност е границата на интервала на сходимост на метода на простата итерация

.

Вече знаем това неравенство. Тя е получена по-рано от теоремата на Самарски като достатъчно условие за сходимост. Допълнителен анализ, базиран на лема 2, ни позволява да прецизираме резултата. Сега установихме, че принадлежността на итерационния параметър интервалът е необходимо и достатъчно условие за сходимост на метода на простата итерация.

Нека се обърнем към изследването на скоростта на конвергенция на метода. Оценката на грешката показва, че тя намалява по закона на геометричната прогресия със знаменател

.

Разгледайте фиг. 2, което ще ни помогне да анализираме тази формула. Подобно е на фиг. 1, само че показва графики на нефункции
, и техните модули. На малки всички собствени стойности
са положителни, а най-големият от тях е
, който намалява с увеличаване на най-ниската скорост. Въпреки това, преминавайки през дот
собствена стойност
, променяйки знака, става отрицателен. В резултат на това сега модулът му се увеличава не намалява, а се увеличава
приближаване до пределната стойност на единството.

Намерете в сегмента
точка , в която намаляващата функция
в сравнение с нарастваща функция
. Определя се от уравнението

което дава

.

В резултат на това получаваме:

Най-малката му стойност е матричната норма достига при
:

.

Формулата показва, че за лошо обусловена матрица, дори при оптимален избор на параметъра на итерация
матрична норма е близо до единица, така че сходимостта на метода на простата итерация в този случай се оказва бавна.

В заключение отбелязваме, че формулата, която определя границата на интервала на конвергенция , и формулата за оптималната стойност на итеративния параметър представляват предимно теоретичен интерес. Обикновено при решаване на SLAE най-голямото и най-малкото характерни числа на матрицата са неизвестни, така че изчислете количествата и не е възможно предварително. В резултат на това итеративният параметър често е необходимо да се избира директно в процеса на изчисления чрез проба и грешка.

Задача 2.

Да разгледаме система от две уравнения с две неизвестни

и конструирайте приблизително решение за него, като използвате метода на простата итерация.

Нека веднага напишем решението на системата

,
,

за да можете след това да го сравните с членовете на итеративната последователност.

Нека се обърнем към решението на системата чрез метода на простата итерация. Матрицата на системата има формата

.

Той е самосвързан и положително определен, тъй като

Нека съставим характеристичното уравнение за матрицата и намерете корените му:

,

,

Те могат да се използват за определяне на границата на интервала на конвергенция и оптималната стойност на параметъра на итерацията :

,
.

За да конструираме итеративна последователност, ние избираме някаква стойност на итеративния параметър на интервала на конвергенция, например,
. В този случай рекурентната формула за членовете на итеративната последователност приема формата:

, където

Вземете най-простото първоначално приближение
и напишете първите няколко термина от итеративната последователност , като за всеки от тях се изчислява несъответствието
. В резултат на това получаваме:

,
,
,

,
,
,

,
,
,

,
,
.

Нормата на остатъците, макар и бавно, но намалява, което показва конвергенцията на процеса. Същото може да се види от сравнението на членовете на итеративната последователност с решението на системата. Бавната конвергенция се дължи на лошата условност на матрицата :

.