Анализ на итеративни методи за решаване на SLAE

Численоторешаване на системи от линейни алгебрични уравнения (SLAE) е една от най-често срещаните задачи в научните и технически изследвания, математическата физика (числово решаване на диференциални и интегрални уравнения), икономиката и статистиката. Поради това в съвременната изчислителна математика се обръща много внимание на методите за решаване на линейни алгебрични уравнения.

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

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

Много внимание се отделя на изучаването на методите за решаване на системи от линейни алгебрични уравнения в съвременната математика. Сред учените, чиито научни интереси са посветени на този проблем, трябва да се откроят С. Годунов, В. Воеводин, А. Островски, Дж. Форсайт, К. Молер и др. В същото време не се обръща достатъчно внимание на сравнението на итеративни и директни методи за решаване на SLAE с помощта на компютърна технология. Това налага допълнително разглеждане на този въпрос по отношение на разработването на критерии за сравнение, препоръки за избор на оптималнометод на решение и др.

Въз основа на това целта на статията е да се разработи алгоритъм за избор на методи за решаване на SLAE с помощта на компютърна технология въз основа на сравнителен анализ на директни итеративни методи.

За да можем да сравним тези методи, нека обобщим системата от критерии. Според изследването на В. Воеводин [3, с. 85], D. McCracken [7, p. 297], резултатите от решаването на системата от линейни уравнения (1), получени както чрез точни, така и чрез итеративни методи, имат определена степен на грешка, което изисква оценка на този параметър за всеки от методите.

Това ни позволява да отделим изчислителната грешка като отделен критерий за сравняване на методите за решаване на SLAE.

При избора на един или друг метод за решаване на SLAE е важно да се вземе предвид обхватът на директните и итеративните методи. Това се дължи на факта, че не всеки метод дава възможност да се получи гарантиран резултат за определена система от линейни уравнения, което е отбелязано в техните трудове от В. Жигулская [6], С. Годунов [4]. Поради това е препоръчително да се отдели като друг критерий за сравнение обхватът на метода на решение SLAE.

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

По този начин критериите за сравняване на точни и итеративни методи за решаване на SLAE с помощта на компютърна технология ще бъдат:

обхват на метода;
време, прекарано в решението;
грешка в резултата.

Нека направим сравнение по избраните критерии. Както се казаПреди това използването на един или друг метод за решаване на система от линейни алгебрични уравнения е ограничено от обхвата на този метод. По този начин много точни методи имат универсален характер (схема на Гаус, схема на Йордан и др.) И се използват за общи неизродени системи, а някои са разработени за специфични системи (точни клетъчни методи за решаване на големи системи от линейни уравнения), което налага определени ограничения върху тяхното използване.

В допълнение, обхватът на приложение на методите за решаване на SLAE е ограничен от вида на матрицата A на системата (1) и на първо място от нейната размерност.

Известно е, че приложните проблеми често изискват решаване на големи и свръхголеми SLAE с повече от 1000 неизвестни.Такива SLAE, например, са резултат от численото решаване на двуизмерни и особено триизмерни проблеми на математическата физика, при които условията на физическа и геометрична апроксимация на двуизмерна и триизмерна област диктуват използването на достатъчно фина изчислителна мрежа с голяма брой изчислителни възли по линейното измерение. Анализ на произведения [1; 2; 5] показва, че е целесъобразно да се решават мащабни задачи на SLAE чрез итеративни методи, тъй като използването на директни методи е невъзможно поради ограниченията на наличната компютърна RAM, а също и поради необходимостта от извършване на прекалено голям брой аритметични операции.

В [3; 6; 7]. Използването на тези методи прави възможно запазването на свойството за разреденост на матрицата. Използването на директни методи за такива системи води до факта, че голям брой нулеви елементи се превръщат в ненулеви и матрицата губи разрядност.

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

Нека сравним директните и итеративните методи по отношение на разходите за време. При внедряване на алгоритми на директни методи за решаване на системи от линейни уравнения с размерност N на езици от високо ниво трябва да се има предвид, че броят на аритметичните операции за умножение ще бъде N 3 . За системи с размери, тази кубична зависимост води до голямо количество време при решаване дори на най-модерните N> 1000 компютри.

Итеративните методи за решаване на SLAE са много по-икономични по отношение на компютърното време. Така че, ако итеративният метод е бързо конвергентен с броя на итерациите m 2 . Тези разходи са по-ниски, в сравнение с точните методи, с N/m пъти за реални и 2N/m пъти за сложни SLAE.

Като пример, на фиг. Фигура 1 показва зависимостта на времето за решаване от размерността на матрицата за решаване на SLAE по методите на Гаус и Зайдел.

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

Ориз. 1. Зависимост на времето за решение от размерността на матрицата при използване на директен и итеративен метод

Нека анализираме директните и точни методи за решаване на SLAE според критерия за грешка на получените резултати от решението. Точните методи за решаване на SLAE се характеризират с грешка при закръгляване, която може да възникне по време на изчислението, както и в процеса на внедряване на тези методи на компютър. В този случай, поради ограничената битова мрежа на компютъравъвеждат се грешки при закръгляване при задаване на вектор b и матрица A. Всичко това води до получаване не на точно, а на приблизително решение на системата Ax = b. И така, в проучванията на V.V. Воеводин, използвайки метода на Гаус като пример, се доказва, че относителната грешка на решението на система (1) е [3, с. 85]:

където: n е редът на матрица A;

t е броят на двоичните цифри на мантисата на числото на използвания компютър.

Например за персонални компютри 2 −t ≈ 10 −7 . От своя страна номерът на условието на матрицата A, който характеризира степента на зависимост на относителната грешка на решението от относителната грешка на дясната страна, е:

В случай на итеративни методи, чиято същност е, че решението на система (1) се намира като граница на последователни приближения x (n) катоn → ∞, където n е номерът на итерация, изисква задаване на началната стойност на неизвестните x (0) и точността на изчислението e>0. Изчисленията се извършват до приключване на оценката.

Основното предимство на итеративните методи е, че е посочена точността на желаното решение. Броят итерации n=n(e), които трябва да се извършат за получаване на дадена точност e, е основната оценка за качеството на метода. Това число се използва за сравняване на различни итеративни методи.

Нека обобщим сравнителния анализ на точните и итеративни методи за решаване на SLAE според критериите, посочени по-горе в табл. 1.

Характеристики на използване на директни и точни методи за решаване на SLAE за внедряване на компютър

Критерий за сравнение	Директни методи	Итеративни методи
Обхват на метода	неефективни при решаване на матрици с големи размери поради извършването на прекомерен брой аритметични операции; водят до загуба на свойството разреденост в разредените матрици. обхватът зависи от свойството на конвергенция; са ефективни при решаване на разредени матрици и матрици с голяма размерност.	обхватът зависи от свойството на конвергенция; са ефективни при решаване на разредени матрици и матрици с голяма размерност.
Времеви разходи	води до необходимостта от отделяне на много време при решаване на системата поради кубичната зависимост на броя на аритметичните операции от размера на матрицата икономичен по отношение на машинното време и използването на RAM, тъй като времето за решение е пропорционално на квадрата на размера на матрицата.	икономичен по отношение на машинното време и използването на RAM, тъй като времето за решение е пропорционално на квадрата на размера на матрицата.
Грешка в резултата	няма информация за точността на полученото решение;	правят възможно получаването на решение с произволна точност.

Въз основа на избраните характеристики на директни и точни методи на SLAE ще разработим алгоритъм за избор на метод за решение на система от линейни алгебрични уравнения (фиг. 2).

Ориз. 2. Блокова схема на алгоритъма за избор на метод за решаване на SLAE

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

разходи, допустима грешка. В резултат на сравняването на тези методи според тези критерии бяха получени следните заключения.

При решаване на разредени матрици и матрици с големи размери (N> 1000), препоръчително е да се използваитеративни методи. Използването на тези методи води до спестяване на компютърно време и RAM. Ограничаващият фактор обаче е възможността за различен итеративен процес, който не позволява постигането на желания резултат. В този случай единственият вариант е да се използват директни методи. В същото време както точните, така и итеративните методи се характеризират с известна грешка в резултата.

Въз основа на анализа е разработен алгоритъм за избор на метод за решаване на SLAE. Окончателното решение за използването на итеративни или директни методи за решаване на SLAE обаче трябва да бъде взето въз основа на анализ на структурата на изучавания математически проблем.

Литература

1.Бахвалов Н.С. Числени методи / Н.С. Бахвалов. – М.: Наука, 1975. – 468 с. 2.Баландин М. Ю. Методи за решаване на високомерни SLAE. / М.Ю. Баландин, Е.П. Шурин.–Новосибирск: Издателство на NSTU, 2000. – 70 с. 3.Воеводин В.В. Матрици и изчисления / В.В. Воеводин, Ю.А. Кузнецов. -М .: Наука, 1984. - 450 с. 4.Годунов С.К. Решение на системи от линейни уравнения / С.К. Годунов - Новосибирск: Наука, 1980. - 250 с. 5. Джордж А. Числено решение на големи редки системи от уравнения / Джордж А., Дж. Лиу. – М.: Мир, 1984. – 390 с. 6.Жигулская В. Ю. Числени методи / Жигулская В. Ю. - Луганск: Alma Mater, 2005 г. - 137 с. 7.McCracken D. Числени методи и програмиране на Fortran / McCracken D., W. Dorn.– М.: Мир, 1977 – 579 p.