Числено решаване на системи от линейни алгебрични уравнения. Достатъчни условия за конвергенция на итеративен процес

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

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

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

Система от линейни алгебрични уравнения

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

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

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

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

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

От първото уравнение на системата изразяваме неизвестното х 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 са минимумът и максимумът собствени стойностиматрица А. Оптималният избор е параметърът

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

Пример 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.

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

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

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

,
,

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

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

.

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

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

,

,

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

,
.

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

, където

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

,
,
,

,
,
,

,
,
,

,
,
.

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

.

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

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

За да се приложи итерационният метод, оригиналната система (2.1) или (2.2) трябва да се редуцира до формата

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

, к = 0, 1, 2, ... . (2.26а)

Матрица Жи векторът се получават в резултат на преобразуването на система (2.1).

За конвергенция (2.26 а) е необходимо и достатъчно за |l аз(Ж)| < 1, где lаз(Ж) са всички собствени стойности на матрицата Ж. Конвергенция ще се получи и ако || Ж|| < 1, так как |lаз(Ж)| < " ||Ж||, където " е произволен.

Символ || ... || означава нормата на матрицата. При определяне на стойността му най-често се спират на проверка на две условия:

||Ж|| = или || Ж|| = , (2.27)

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

. (2.28)

Ако (2.27) или (2.28) е изпълнено, итерационният метод се сближава за всяко първоначално приближение. Най-често векторът се приема или нула, или единица, или самият вектор се взема от (2.26).

Има много подходи за трансформиране на оригиналната система (2.2) с матрицата НОза да се осигури формата (2.26) или да се удовлетворят условията за сходимост (2.27) и (2.28).

Например (2.26) може да се получи по следния начин.

Позволявам НО = AT+ ОТ, дет AT№ 0; тогава ( б+ ОТ)= Þ б= −° С+ Þ Þ б –1 б= −б –1 ° С+ б–1 , откъдето = − б –1 ° С+ б –1 .

поставяне - б –1 ° С = Ж, б–1 = , получаваме (2.26).

От условията за сходимост (2.27) и (2.28) се вижда, че представянето НО = AT+ ОТне може да бъде произволно.

Ако матрицата НОудовлетворява условия (2.28), то като матрица ATможете да изберете долния триъгълник:

, a ii ¹ 0.

; Þ ; Þ ; Þ

Избирайки параметъра a, можем да гарантираме, че || Ж|| = ||д+ а А|| < 1.

Ако преобладава (2.28), тогава трансформацията към (2.26) може да се извърши чрез решаване на всеки азто уравнение на системата (2.1) по отношение на x iсъгласно следните рекурсивни формули:

(2.28а)

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

Като пример, помислете за системата

(2.29)

Както може да се види, в уравнения (1) и (2) няма диагонална доминация, но в (3) има, така че го оставяме непроменен.

Нека постигнем диагонална доминация в уравнение (1). Умножете (1) по a, (2) по b, добавете двете уравнения и изберете a и b в полученото уравнение, така че да има диагонална доминация:

(2a + 3b) х 1 + (-1,8a + 2b) х 2 +(0,4a - 1,1b) х 3 = а.

Като вземем a = b = 5, получаваме 25 х 1 + х 2 – 3,5х 3 = 5.

За да трансформираме уравнение (2) с доминиране (1), умножаваме по g, (2) умножаваме по d и изваждаме (1) от (2). Вземете

(3d - 2g) х 1+(2d+1.8g) х 2 +(-1.1d - 0.4g) х 3 = −g .

Поставяйки d = 2, g = 3, получаваме 0 х 1 + 9,4 х 2 – 3,4 х 3 = -3. В резултат на това получаваме системата

(2.30)

Тази техника може да се използва за намиране на решения за широк клас матрици.

или

Вземайки като първоначално приближение вектора = (0,2; -0,32; 0) T, ще решим тази система с помощта на технология (2.26 а):

к = 0, 1, 2, ... .

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

.

Итеративна технология за решение на формуляра (2.26 а) е кръстен чрез проста итерация .

Степен абсолютна грешказа метода на проста итерация:

където символ || ... || означава нормата.

Пример 2.1. Използвайки метода на простата итерация с точност e = 0,001, решете системата от линейни уравнения:

Броят на стъпките, които дават отговор с точност до e = 0,001, може да се определи от връзката

£0,001.

Нека оценим сходимостта по формула (2.27). Тук || Ж|| = = max(0,56; 0,61; 0,35; 0,61) = 0,61< 1; = 2,15. Значит, сходимость обеспечена.

Като първоначално приближение вземаме вектора на свободните членове, т.е. = (2,15; -0,83; 1,16; 0,44) T. Заменяме стойностите на вектора в (2.26 а):

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

к	х 1	х 2	х 3	х 4
	2,15	–0,83	1,16	0,44
	2,9719	–1,0775	1,5093	–0,4326
	3,3555	–1,0721	1,5075	–0,7317
	3,5017	–1,0106	1,5015	–0,8111
	3,5511	–0,9277	1,4944	–0,8321
	3,5637	–0,9563	1,4834	–0,8298
	3,5678	–0,9566	1,4890	–0,8332
	3,5760	–0,9575	1,4889	–0,8356
	3,5709	–0,9573	1,4890	–0,8362
	3,5712	–0,9571	1,4889	–0,8364
	3,5713	–0,9570	1,4890	–0,8364

Конвергенцията в хилядни става още на 10-та стъпка.

Отговор: х 1 » 3,571; х 2 » -0,957; х 3 » 1,489; х 4"-0,836.

Това решение може да се получи и с помощта на формули (2.28 а).

Пример 2.2. За да илюстрираме алгоритъма с помощта на формули (2.28 а) разгледайте решението на системата (само две итерации):

; . (2.31)

Нека трансформираме системата до вида (2.26) съгласно (2.28 а):

Þ (2.32)

Да вземем първоначалното приближение = (0; 0; 0) T. Тогава за к= 0 очевидно стойност = (0,5; 0,8; 1,5) T. Нека заместим тези стойности в (2.32), т.е к= 1 получаваме = (1,075; 1,3; 1,175) T.

Грешка e 2 = = max(0,575; 0,5; 0,325) = 0,575.

Блокова схема на алгоритъма за намиране на решението на СЛАУ по метода прости итерациипо работни формули (2.28 а) е показано на фиг. 2.4.

Характеристика на блоковата диаграма е наличието на следните блокове:

- блок 13 - предназначението му е разгледано по-долу;

- блок 21 - извеждане на резултатите на екрана;

– блок 22 – проверка (индикатор) на конвергенция.

Нека анализираме предложената схема на примера на система (2.31) ( н= 3, w = 1, e = 0,001):

= ; .

Блокирайте 1. Въведете първоначалните данни А, , ш, д, н: н= 3, w = 1, e = 0,001.

Цикъл I. Задайте началните стойности на векторите х 0ази x i (аз = 1, 2, 3).

Блокирайте 5. Нулирайте брояча на броя повторения.

Блокирайте 6. Нулирайте текущия брояч на грешки.

ATцикъл II променя номерата на редовете на матрицата НОи вектор.

Цикъл II:аз = 1: с = b 1 = 2 (блок 8).

Отидете до вложен цикъл III, блок 9 - брояч на номерата на колоните на матрицата НО: й = 1.

Блокирайте 10: й = аз, следователно се връщаме към блок 9 и увеличаваме йза единица: й = 2.

В блок 10 й ¹ аз(2 № 1) - отидете на блок 11.

Блокирайте 11: с= 2 – (–1) × х 0 2 \u003d 2 - (-1) × 0 \u003d 2, отидете на блок 9, в който йувеличете с едно: й = 3.

В блок 10 условието й ¹ азизпълнено, така че отидете на блок 11.

Блокирайте 11: с= 2 – (–1) × х 0 3 \u003d 2 - (-1) × 0 \u003d 2, след което отиваме в блок 9, в който йувеличете с едно ( й= 4). Значение йПовече ▼ н (н= 3) – край на цикъла и отидете на блок 12.

Блокирайте 12: с = с / а 11 = 2 / 4 = 0,5.

Блокирайте 13: w = 1; с = с + 0 = 0,5.

Блокирайте 14: д = | x i – с | = | 1 – 0,5 | = 0,5.

Блокирайте 15: x i = 0,5 (аз = 1).

Блокирайте 16. Проверете състоянието д > де: 0,5 > 0, следователно, отидете на блок 17, в който присвояваме де= 0,5 и връщане по препратка " НО» към следващата стъпка от цикъл II - към блок7, в който азувеличаване с едно.

Цикъл II: аз = 2: с = b 2 = 4 (блок 8).

й = 1.

През блок 10 й ¹ аз(1 № 2) - отидете на блок 11.

Блокирайте 11: с= 4 – 1 × 0 = 4, отидете на блок 9, в който йувеличете с едно: й = 2.

В блок 10 условието не е изпълнено, затова преминаваме към блок 9, в който йувеличете с едно: й= 3. По аналогия преминаваме към блок 11.

Блокирайте 11: с= 4 – (–2) × 0 = 4, след което завършваме цикъл III и преминаваме към блок 12.

Блокирайте 12: с = с/ а 22 = 4 / 5 = 0,8.

Блокирайте 13: w = 1; с = с + 0 = 0,8.

Блокирайте 14: д = | 1 – 0,8 | = 0,2.

Блокирайте 15: x i = 0,8 (аз = 2).

Блокирайте 16. Проверете състоянието д > де: 0,2 < 0,5; следовательно, возвращаемся по ссылке «НО» към следващата стъпка от цикъл II – към блок7.

Цикъл II: аз = 3: с = b 3 = 6 (блок 8).

Отидете на вложен цикъл III, блок 9: й = 1.

Блокирайте 11: с= 6 – 1 × 0 = 6, отидете на блок 9: й = 2.

През блок 10, преминаваме към блок 11.

Блокирайте 11: с= 6 – 1 × 0 = 6. Завършете цикъл III и отидете на блок 12.

Блокирайте 12: с = с/ а 33 = 6 / 4 = 1,5.

Блокирайте 13: с = 1,5.

Блокирайте 14: д = | 1 – 1,5 | = 0,5.

Блокирайте 15: x i = 1,5 (аз = 3).

Съгласно блок 16 (като се вземат предвид препратките " НО" и " ОТ”) излезте от цикъл II и отидете на блок 18.

Блокирайте 18. Увеличете броя на повторенията то = то + 1 = 0 + 1 = 1.

В блокове 19 и 20 от цикъл IV заместваме първоначалните стойности х 0азполучени стойности x i (аз = 1, 2, 3).

Блокирайте 21. Печатане междинни стойноститекуща итерация, в този случай: = (0,5; 0,8; 1,5) T, то = 1; де = 0,5.

Отидете на цикъл II на блок 7 и извършете разглежданите изчисления с нови начални стойности х 0аз (аз = 1, 2, 3).

След което получаваме х 1 = 1,075; х 2 = 1,3; х 3 = 1,175.

Тук, тогава, методът на Seidel се събира.

По формули (2.33)

к	х 1	х 2	х 3
	0,19	0,97	–0,14
	0,2207	1,0703	–0,1915
	0,2354	1,0988	–0,2118
	0,2424	1,1088	–0,2196
	0,2454	1,1124	–0,2226
	0,2467	1,1135	–0,2237
	0,2472	1,1143	–0,2241
	0,2474	1,1145	–0,2243
	0,2475	1,1145	–0,2243

Отговор: х 1 = 0,248; х 2 = 1,115; х 3 = –0,224.

Коментирайте. Ако за една и съща система простата итерация и методите на Seidel се сближават, тогава методът на Seidel е за предпочитане. На практика обаче областите на конвергенция на тези методи могат да бъдат различни, т.е. методът на простата итерация се сближава, докато методът на Seidel се разминава и обратно. И за двата метода, ако || Ж|| близо до мерна единица, степента на конвергенция е много ниска.

За ускоряване на конвергенцията се използва изкуствена техника – т.нар метод за релаксация . Същността му се състои в това, че следващата стойност, получена чрез итерационния метод x i (к) се преизчислява по формулата

където w обикновено се променя от 0 на 2 (0< w £ 2) с каким-либо шагом (ч= 0,1 или 0,2). Параметърът w е избран така, че сходимостта на метода да се постигне при минимален брой итерации.

Релаксация- постепенно отслабване на всяко състояние на тялото след прекратяване на факторите, които са причинили това състояние (физ. техн.).

Пример 2.4. Помислете за резултата от петата итерация, като използвате формулата за релаксация. Да вземем w = 1,5:

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

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

Нека първоначалното приближение до корена е известно 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скоростта на конвергенция намалява и постепенно конвергентният процес първо има цикли, след което става дивергентен.