Буслов, Яковлев - Введение в численный анализ (947494), страница 13
Текст из файла (страница 13)
Модифицируем соответствующим образом метод простых итераций, заменив в сумме * компоненты х' на г'э' . Таким образом мы получаем новую итерационную процедуру ~< з>. Такой итерационный процесс называется лгешодом Зейделл. Представим его в матричной форме.
Пусть Š— нижнетре- угольная матрица с элементами а,,у<1 О ,1>1 а П вЂ” верхнетреугольная матрица с элементами -( аб, 1)1 О >у<1 Как и раньше введем матрицу Р = Жид(ап ... анм), тогда А = Р+ Р+ П . В матричном виде метод Зейделя имеет = Р Ь вЂ” Р Тле — Р Пх 5.2.6 Сходимость метода Зейделя Итак, итерации по методу Зейделя должны быть организованы таким образом, чтобы Рх' = Ь вЂ” Ех' — (1х' или х'~' = (Р+Р) 'Ь вЂ” (Р+ Р) '(ух' . Отображение х ь+ (Р Л-Е) 'Ь вЂ” (Рт1) 'Пх является сжатием, если //(Р+ Р) 'Щ < 1, таким образом справедлива Теорема.
Мешод Зейделл сходитвсл, если О(Р+ б) '11О < 1. Условия этой теоремы довольно трудно проверяемы, так как матрица (Р + Е) 'Г должна еще и вычисляться. Существует достаточно простой признак сходимости метода Зейделя, который связан с понятием положительной определенности матрицы относительно скалярного произведения. Напомним, что оператор А, действующий в евклидовом пространстве Е называется положительно определенным, если (Ах, х) > у(х, х) . Т > О .
Если оператор положительно определен, то у него существует и обратный и он также положительно определен. Также важно отметить, что если оператор А положительно определен и симмезричен в Вл, то форма (х, у)л = (Ах, у) удовлетворяет всем свойствам скалярного произведения. В дальнейшем факт положительной определенности оператора А будем обозначать: А > О . Заметим, что в комплексном евклидовом пространстве факт положительной определенности аператора А автоматически влечет за собой зрмитовостйк А = А*.
Теорема (достаточный признак скодимости метода Зейделя). Метод Зейделл сходитсл в вещественном ввклидоввм пространстве если А си метпричн л положительно опрвделеннав матрица. Для доказательства этой теоремы нам потребуется следующая Лемма. Пусть последовательность векторов кй определена рекурентнмм соотношением В(гнм — к )-гАг =О, (3) вде  — -' А > О, А > О , тогда кй -э О . Доказательство.
Представим х в виде г = — (г +я ) — — (г — я ) й ! й.н й ! й.н й 2 2 и подставим это предсзавление в (3), тогда В(гйт' — яй) + — А(гйт' + гй ) — — А(гйт' — гй) = О 2 2 или ( — -А)(гй+' — кй) + -А(хй"'+ к') = О 2 2 Умножим это равенство скалярно иа г~~~ — х, тогда О = (г ~' — гй1в-лГз + — (А(гйэ'+ г '),гйэ' — к ) = 2 = (к — к )и лзз -~- — ()г (А — )г (л) = О где ~ ~л = (А, ), ( )в-к~э = (( — А/2)ч ) — нормы, определяемые операторами А и  — А/2 соответственно. Из последнего равенства в силу положительной определенности оператора ( — А/2) следует что )г (л — )к (л < О, т.е.
йэй й последовательность )к" (з невозрастающан: )г"+')л < (г~)л . При этом последовательность чисел )к~(з ограничена снизу поскольку (г )л > О . Таким образом существует конечный предел !пп )г )л = а . Но тогда из того же равенства й й й-~ следует, что норма ~кй"' — хй~!в 1й! стремится к нулю, а значит и кй+' — кй -й О, к -э сю . Вернемся теперь к определению последовательности кй: Акй = — В(кйэ' — хй) откуда кй = — А 'В(к '+' — кй) и, следовательно, ))к")) < )(А 'В)! х !)г '+' — г )( -э О, и таким образом кй -э О, при к -э со. 67 Приступим теперь собственно к доказательству досгаточного признака скодимости метода Зейделя, Как нетрудно видеть, метод Зейделя (Р Ч-?)х'т' -Ь Пх' = Ь может быть представлен в виде (Р+ Е)(х'т' — х') + Ах' = Ь .
Пусть и — точное решение уравнения Ап = Ь, оно существуег, так как А — положительно определенный оператор и, следовательно, обратим. Положим также в' = х' — и, тогда (Р+ Т)(в'~' — г') + Ая' = О . Убедимся в том, что (Р + Т вЂ” -А) положительно определенная матрица если А симметрична иположнтельно 1 определена. Действительно Р+Х вЂ” — А=Р+Š— — (Р+1+П) = — (Р+Т вЂ” Г) 1 1 1 2 2 2 Рассмотрим соответствующую квадратичную форму ((Р + Т вЂ” П)х, х) = (.Рх, х) + (Т х, х) — (Т х, х) Заметим, что поскольку А симметричная матрица, следовательно Е = с? и т (? х, х) = (х, Т х) = (х, 1?х) = (с?х, х), поэтому ((Р+Х вЂ” Цх,х) = (Рх,х) = ~ ачт; > О, поскольку у положительно определенной матрицы все диагональные элементы больше нуля (почему?): ае > О . Таким образом мы находимся в условиях Леммы, и, следовательно, последовательность я' стремится к нулю, откуда следует, что последовательность х' = и -Ь х' стремится к истинному решению и, Глава 6 Алгебраические спектральные задачи 6.1 Некоторые сведения из матричной теории Пусть А линейный оператор действующий в вещественном В.~ шгн в комгшексном С Евклндовом пространстве: А.
Вн(Сн) -+ ге~(С ) . Число Л и вектор х называются соответственно собственным числом (значением) и собственным вектором оператора А отвечающим собственному числу Л, если Ах = Лх . В частности, справедливы следующие теоремы. Теорема У.всякий линейный оператор в С имеет по крайней мере одно собственное зна гение. Теорема 2.
Собственные векторы, отвечающие различным собственным значениям линейно независимы. Теорема 3. Длл любого набора из йс линейно независ мык векторов е',е,,е (базиса) суи~ествуст единст- еенный дральный базис е',ег,...,е, такой что (е',сед) = б„. Заметим, что всякий ортонормнрованный базис самодуален. Пусть А имеет Х различных собственных векторов х', тогда они образуют базис, и, следовательно, существует дуальный базис х' . В этом случае, как нетрудно убедиться, сопряженный оператор А" (в случае вещественного евклидова пространства просто транспоннрованная матрица Ат ) имеет в качестве собственных значений числа Л,, а е качестве собственных векторов — векторы дуального базиса. Ах' = Л,х', А" х' = Л;х' .
Действительно (х', Л,х') = (Лх', х*) = (Ах*, х') = (х', А*х') и, аналогично (хг, А*х*) = О, ъ ф у, то есть (хз, А" х') = 6;г (хз, Лхз ) . Кроме того, нетрудно показать справедоивость следующего спектрального разложения оператора А: А = ~~~ Л,(,х')х' = ~~~ Л,Р, .=1 .=1 где операторы Р, = (эх')х' — суть собственные проекторы оператора А . В самом деле, произвольный вектор г можно разложить по собственным векторам оператора А: г" = 2 (з,х')х* . Тогда Аг = ~(г" х )Ах* = ~(з х ) Л х' = ~ Л Е',У . Пусть А = А — эрмнтова матрица (в В.н — симметричная). В этой ситуация собственные значения вещественны, алгебраическая и геометрическая кратности любого собственного значения совпадают, собственные векторы х', отвечающие различным собственным числам ортогональны, и существует ортонормированвый базис из собственных векторов.
В случае однократно вырожденного собственного значения Л отвечающий ему собственный проектор Р одномерен и имеет вид Р = (, х)х (всюду считаем, что собственный вектор х нормирован на единицу). Вели надпространство решений Ах = Лх более чем одномерно, то в нем выбирается произвольный ортобазнс х' и собственный проектор отвечающий собственному числу Л представляет собой сумму соответствующих одномерных проекторов Р = ~ (, х')х' . Отметим (легко проверяемое) важное свойство ортогональнл»х проекторов; Р,Рь = »»мР, . Степень оператора имеет сле»»ующую запись через ортогональные проекторы А = ~~» Лх.
(А)Рх . ь Многочлены от оператора определяются как сумма соотвесствуюн»их степеней. Поскольку многочленами можно при- близнть любую функцию> то функцию от оператора естественно определить как У(А) = »у у(Л„)Р„. э Собютвенные функции у оператора и у функции от оператора совпадают, тогда как собственные значения функции от оператора есть числа г(Лх). 6.2 Собственные числа эрмитовых матриц 6.2.1 Интерполяционный метод Поскольку собственные числа Л, матрицы А являются корнями характеристического полннома Ря(Л) = »)е$(А — Л1), то можно вычислить Ря(Л) в (и+1)-ом наугад выбранном значении Л (их естественно выбирать в промежутке ( — )~А) ~» ))А~)), если границы спектра известны; оценить их можно по максимальному.
по модулю элементу матрющы) и построить по ним интерполяционный полипом степени п, который совпадает собственно с характеристическим, после чего определяются его корни. Этот метод применим и для неэрмитовых матриц (при соответствующем выборе метода определения корней). 6.2.2 Нахождение максимального по модулю собственного значения Для удобства будем считать, что собственные числа пронумерованы в порядке убь»валия их модуля. а) Метод итераций Пусть К = К вЂ” произвольный нювзльный вектор. Определим последовательность о к" =А !~к~"-Ч! !~А"-'к~! тогда й ~~к'"'~~ = ~л „.~ . Доказательство: Действительно К = ) Рьй, )))К () = (ГЛЯ-вк$» и К ~ ~ЛьРьК Л а (Р» хК ~ ~(Лу„/Л аае) РьК) ьм» Пусть Л' — собственное число, следующее за максимальным по модулю. Тогда //А ф/~ =(А"к,А"к) =Л~"„.
((Р „к,к)+0((Л/Л „]' )), 70 = ]Л .„](1-~О([Л'/Л ..]'-2)), Таким образом если стартовый вектор к имел ненулевую проекцию на собственное подпространство отвечающее максимальному по модулю собственному значению (то есть Р „я ~ 0 ), то приведенная итерационная процедура приводит к нахождению Л „. Однако, хотя формально, предыдущее рассмотрение верно лишь в случае ненулевой проекции, в действительности из-за ошибок округления при вычию2ениях эта проекция наверняка появится на некотором шаге и дальнейшее применение метода итера2щй приведет к желаемому резульрату, Попутно заметим, что ею2я подпространство отвечающее Л, одномерно, то метод итераций одновременно приводит к нахождению собственного вектора хм" 2 отвечающего Л .
Этим вектором с точностью до нормировки является х~"' = 11ш йв -2 С:2 Замечание. Для нахождения Лы можно применять метод итераций и в более простой постановке. Пусть 1-ая компонента в максимального собственного вектора в стаццартном евклидовом базисе не равна нулю (хотя бы одна такая существует), тогда (А" к)1 Лы„, = йю б) Метод следов Известно, что след матрицы (сумма диагональных элементов) равен сумме ее собственных значений с учетом кратности: Л, = ТгА, таким образом ~ Л~ = ТгА, и, следовательно ТгА = Л„,„2(1 + (Л'/Л„„„) А-...], где Л' — следующее по модулю за максимальным собственное зню2ение.
'Хаким образом Л „, можно искать как следующий предел ]Лтла2] = 11т '"/Т~А"' или, например, в виде ТгА т' Л аа2 = 122п 22-222 ТгА Процедуру возведения матрицы в степень можно оптимизировать: АхАхАхА, А2 А2 22 и так далее, в частности А'е = (Аз) 2 = Аэ в) Метод скалярных произведений Этот метод является обобщением метода итераций.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
