Фаддеев, Фаддеева - Вычислительные методы линейной алгебры (947503), страница 74
Текст из файла (страница 74)
В табл. Ч!. 2! дается решение системы методом ортогонализации строк. Таблица заполняется по схеме Аг Аг Аз Аз А~аз Агз, Абхаз А~аз Х Л Зг Уз г'з г з Ег г з Контроль (А'з; А'з ) (А'зо А'з ) (А'зо Аз) ! П Ш !Ч Ч! ТВ аг аз аз аз А'АХ= А'Е, 6. Метод А'А-минимальных итераций. Здесь А неособенная матрица, И=А'А г. =до Ез=йдо Ея=гсл зз)о' С= — А', В=Е, )с,=-)т. Формулы метода и пример даны в 9 65. 7. Метод АА'-минимальных итераций.
Здесь А неособенная матрица, Й=АА', Лз= уз, Лг=Вуз,..., Л„=)с"- дз; С=Е, В = А'. Иг =- Е. Формулы метода и пример даны в 6 65. 8. Метод сопряженных градиентов после первой трансформации Гаусса. Пусть А неособенная матрица. Применение метода сопряженных градиентов к системе [ГЛ. И4 МЕТОД МИНИМАЛЪНЫХ ИТЕРАЦИИ О О О О О М О С 4 О О СО О С СС СС 4 О О Ос сО СС О О О О О 'С СС СО О И С "4 О О О О 'С' О О О Й О СО О О О 1 О И С'4 О О О О О 4" ОС О И О О Ф й О СС ОС ОИ О ~ 'О б О И С О ИОЛА ОС Я ОС СО О С'4 СО СС ОООО С4 О 4 СС О С- О О О О С 4 СС б 4 О О Ф О б о ! О О О С ОС О б О С' Ос О О СО 'С' ОС ! ОС О С4 СС ОС О Ф сО СС Я С О О О НЕКОТОРЫЕ МЕТОДЫ О,й~й О О О О ! ! ! ! О О с 6 сс О М сс, сс О О О ф сч со1 о» О О О О ! со О» О Ф О с» сс О» О О О Ф с со О О с- О! О» О сО О» О с» О !' сс с»» со с О СО С сО со сс СЛ О О со с! О О О С»ООО 'О 3 Я Ф ф со О О О О О О О О с» с'» с» О.
с! С- О О О О 1 Ф» ФФ сс со О О О О О О » О О» О О О О» О О О» Я О с! » 8 3$Й О О О О 1 й» 3.~ О ОООО О О ! О со СО сО О О О О О О ЯО» О С! О О Ю й сс с О, » К .с с О !' О О с с'» ! со ! О» сО О со с О О О О Ф 8 О О О Я сс1 со ф с» Ой-= О О ЯВФ О О О О 1 ! сО с'» с» со » с! с» ~й1~ сО» !.- О! О О О О М ! а с а. и М сс с К с О О с О М с ! М М с:! с О К М О О М с О и й О »Т М О М СОПРЯЖЕННЫХ НАПРАВЛЕНИЙ 451 452 метод минимальных итввлций [гл. ж полученной из системы АХ=Р первой трансформацией Гаусса дает Х= — Хе+ ~~'., а;з; (гг — ! ге-!) (зь А'Агч) л~ = — го г; = г,, — а;А'Аг; з;, = г;+ Ьгл; Ь (г гг) (г; и ~.~ т) Здесь гг невязка преобразованной системы. Ясно, что гг = А'га где гг невязка исходной системы.
Принимая это во внимание и преобразуя скалярные произвеления, придем к следуюшим расчетным формулам: Х= — Х + .'5',а л; 1 1 (А'г~ ь А'гг г) (Аль Ага) г, = А'го, ге= г,,— а;Аз~ (22) г„, = — А'гг+ Ь,з; (А'га А'г;) (А'ге и А'гг,) Метод контролируется выполнением условиИ ортогональности (А'го А'г~) = О. В табл.
Ч1. 22 приводится иллюстративный пример с данными табл. П. 1. 9. Метод сопряженных градиентов после второй трансформации Гаусса. Пусть А неособенная матрица. Применение метода сопряженных гпадиентов к вспомогательной системе АА')'= г, 453 ф 691 НЕКОТОРЫЕ МЕТОЛЫ СОПРЯЖЕННЫХ НАПРАВЛЕНИЙ О О О О О О с- сч О СЧ СО б О ь я О О Д О СО СЧ СС СО О О О С- О СО О СЬ сь сс О б ' О с О О О СЧ О О я сс о сч О СО Сч СО СЧ О О О О о о СО С'Ь О С' Сч О СЧ О СЧ СО О о СО " "" 6 Ф ! СО с о О О О О с сч 3433 сь О а о о о О \' О О О О О О ОЪ СЬ О О О О О о сО СО с« Ж О "$з~ о о о о О О О О О О 'О 1 О О О~ сО с' сО О Ос с' сО О О сч о СО СО с'ь Р СО о лО Я СО СЭ й С Ь СО СО сч сь О О СС О С О О О О О ь О, й О й~ О й С й О с н й О й О й СО О С О СЧ сь я с о $ О О О б ! О О СС СО Ь О СЧ СС СС СО Я С' О О О О ! ОООО Я $ СО О 454 [гл.
тп метод минимальных итввлцнй У=У+У р~ 4-1 (гс и гс ~) а!=ге г, = г;,— а;АА'га 8Фе1 г~+ ЬЛ (гь г;) (г~ н г~,) Здесь г; — невязкн преобразованной системы, которые, очевидно, совпадают с невязками исходной системы. Обозначим А'г;=йо Так как Х= А'У, получим после легких преобразований следующие расчетные формулы: Х + р~ л;й) 1-2 (гс о г, ,) (а (,"д А'гд г;,— а Ади А г~+лМ~ (гь г~) (г; и г; ~) ' аз= (23) Очевидно, что (го гл)=0 при ( + (. Последний метод равносилен методу, описанному Крейгом [1[.
хотя несколько отличается от него по вычнслгтельной схеме. В табл. Ч(. 23 дана численная иллюстпация метода для системы табл. П. 1. полученной из исходной системы АХ= Р второй трансформацией Гаусса, дает ГЛЛВЛ Ч!1 ГРАДИЕНТНЫЕ ИТЕРАЦИОННЫЕ МЕТОДЫ вЂ” = — р (!) ятаг! )' (Х), лх где р(Е) любая положительная функция от параметра !. Выбор функции р(!) влияет лишь на параметризацию линии наискорейшего спуска. Например, если при решении системы АХ=Г с положительно- определенной матрнцей А в качестве функционала взята функция ошибок, то уравнение (1) при р(!) =1 будет — = тч — АХ. пХ лт (2) Следовательно, линия наискорейшего спуска будет определяться как решение системы линейных дифференциальных уравнений с постоян- нымн коэффициентами.
В настоящей главе будут изложены итерационные методы, пригодные как для решения линейных систем, так и для решения частичной проблемы собственных значений в случае положительно-определенной матрицы и основанные преимущественно на идее релаксации, ко.горая уже была освещена в гл. П! и Ч. В отличие от методов, изложенных в этих главах, векторами, в направлении которых осуществляется минимизация выбранного функционала„будут не координатные векторы, а векторы. связанные с самим функционалом— именно, это будут градиенты функционала.
Именно такой выбор направлении минимизации связан с тем, что, как известно (п. 1 Я 14 гл. 1), направление, противоположное направлению градиента функционала в данной точке, обеспечивает в окрестности этой точки наиболее быстрое убывание функционала. По этой причине некоторые градиентные методы называются также методами наискорейшего спуска. Идеальным градиентным методом явилось бы построение линии наискорейшего спуска, исходящей из начального приближения и приводящей к точке, дающей минимум функционала, т.
е. линии, направление которой в каждой точке противоположно направлению градиента функционала в этой точке. Дифференциальное уравнение линии наискорейшего спуска есть 466 [гл. чп ГРАДИЕНТНЫЕ ИТЕРАЦИОННЫЕ МЕТОДЫ При выбранной параметризации искомое решение данной алгебраической системы получается как Нш Х(Г), независимо от выбора г+ со начального приближения. Действительно, легко видеть, что общим решением системы (2) является Х= Л"+ е "'С, где Х' точное решение системы АХ= гт, а С произвольный постоянный вектор.
В одношаговых методах наискорейшего спуска траектория наискорейшего спуска, исходящая из данного начального приближения, заменяется ломаной, составленной из отрезков касательных к траекториям наискорейшего спуска, проходящим через вершины этой ломаной (рис. 6). Первым среди градиентных метолов появился метод наискорейшего спуска, предложенный Л, В. Канторовичем [1! и независимо от него Темплем [1!. Детальное изучение этого метода показало в ряде случаев медленную сходимость процесса, и это обстоятельство привело к развитию Рис.
б. других градиентных мето- дов †метод с неполной релаксацией и а-щаговых процессов. Последние процессы естественным образом (именно при а= л) оказались связанными с методом сопряженных градиентов (в случае решения системы) и с методом минимальных итераций (в случае решения проблемы собственных значений).
Таким образом, эти последние методы можно рассматривать как предельные случаи многошаговых методов спуска. В Я 70 — 73 мы рассмотрим итерационные градиентные процессы для решения линейных систем, в Я 74 — 76 для решения частичной проблемы собственных значений. Как правило, матрица А считается в этой главе положительно-определенной. 5 70. Метод наискорейшего спуска для решения линейных систем Пусть А положительно-определенная матрица и пусть АХ= г.
(1) заданная линейная сдстема. В работах Л. В. Канторовича [1! — [3! решение этой системы связывается с задачей отыскания вектора, ф 70) мвтод ноисковвйшвго спгска для ввшвния линвйных систвм 457 дающего минимум функционалу Н(К) = — (АХ, Х) — 2(Г, Х), (2) Н (Хо+ аго) = (АХо+ аАго Хо+ аго) 2 (Р Хо+ аго) = =(АХо Хо)+ 2а(АХо го)+а'(Аго го) — 2(г" Хо) 2а(г", го) = == Н(Хо) 2а (го го) + аа (Аго го) = то это выражение достигает минимума при (го го) а= о= А ( го.
го) и этот минимуи равен Н ( ~; ) (го го)о (Аго го) (4) Итак, Х, = Х, + аого, го = Р— АХо а (го го) (Аго, го) Н(Х,) = Н(Х,)— у(А) — У(Хо) — („,, ) . где Далее определяется Ха=Х,+а,г,. где г,=г" — АХ, и ив (Аго гт) ' отличающемуся лишь постоянным, но заранее неизвестным, слагаемым (АХ*, Х*) от функции ошибки 7'(Х)=(А)', )'). Здесь Х' — точное решение системы, совпадающее с вектором, реализующим минимум Н(Х), г'=Х' — Х вЂ” вектор ошибки. Поставленная задача решается следующим образом.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
