main (1160440), страница 4

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 4)

Примеры и канонический вид итерационных методов решения СЛАУ21Метод РичардсонаМетод Ричардсона определяется итерационной схемой вида+1 − + = , +1 > 0, ∈ Z+ , 0 — задано.+1(8)Замечание. Для итерационных методов (7) и (8) в случае, когда матрица являетсясимметричной и положительно определенной, известен такой набор итерационных параметров (Чебышевский набор), при котором сходимость этих методов будет наиболеебыстрая.Попеременно-треугольный итерационный метод (метод Самарского)Представим матрицу в виде = 1 + 2 ,где 1 — нижнетреугольная⎛0.5110⎜ 210.522⎜1 = ⎜ ....⎝ ..12матрица, 2 — верхнетреугольная матрица:⎞⎛···00.51112···⎟⎜···0 ⎟0.522 · · ·⎜ 0.. ⎟ , 2 = ⎜ ........⎝ ....

⎠.· · · 0.50012...⎞⎟⎟⎟.⎠· · · 0.5Итерационная схема попеременно-треугольного метода имеет вид( + 1 )( + 2 )+1 − + = , > 0, ∈ Z+ ,(9)где > 0, > 0 — итерационные параметры, позволяющие, вообще говоря, ускорить процесс сходимости итерационного метода. Рассматриваемый метод формально является неявным, однако можно показать, что (+1)-ая итерация выражается с помощью явных формулза три шага. Введем обозначения:+1 = ( + 2 )+1 − ,+1 − .Определение.

Вектор = − называется невязкой на -ой итерации. +1 =В нашем случае невязка известна. На первом шаге решим уравнение( + 1 )+1 = .Заметим, что ( +1 ) — нижнетреугольная матрица. Нахождение вектора решения системы с нижнетреугольной матрицей осуществляется по явным формулам, начиная с первойкомпоненты вектора +1 . На втором шаге аналогично решим уравнение с верхнетреугольной матрицей ( + 2 ):( + 2 ) +1 = +1 .На третьем шаге найдем ( + 1)-ую итерацию по формуле+1 = + +1 .Таким образом, несмотря на то, что метод Самарского является неявным, его реализацияне представляет никакой трудности.22§6Глава 1.

Численные методы линейной алгебрыТеоремы о сходимости итерационных методовРассмотрим матричное уравнение вида = ,(1)где || ≠ 0, ( × ), = (1 , 2 , . . . , ) , = (1 , 2 , . . . , ) .Рассмотрим также двухслойный стационарный метод решения уравнения (1):+1 − + = ,(2)где ∈ Z+ , начальное приближение 0 задано, — положительное вещественное число, — обратимая матрица размера ( × ).Чтобы говорить о сходимости итерационного метода, необходимо ввести линейное пространство и определить в нем норму. В курсе линейной алгебры доказывается, что в конечномерном пространстве все нормы эквивалентны. То есть найдутся такие константы, припомощи которых можно выразить одну норму через другую.

Но при исследовании сходимости итерационных методов мы будем устремлять к нулю параметры этих методов, и еслиони будут участвовать в записях констант перехода от одной нормы к другой, то смыслтаких оценок, вообще говоря, может сойти на нет. Поэтому всегда при рассмотрении сходимости итерационных методов мы будем указывать, в какой именно норме производитсяисследование.Пусть — линейное вещественное пространство размерности :dim = .Рассмотрим два произвольных вектора и из этого пространства: ∈ , = (1 , 2 , .

. . , ) , ∈ , = (1 , 2 , . . . , ) .Определим скалярное произведение двух векторов, заданных в ортонормированном базисепространства :∑︁(, ) = .=1Введем евклидову норму:‖‖ =√︀(, ) =(︃ ∑︁)︃ 122.=1Эту норму также часто называют среднеквадратичной нормой.Далее будем считать, что понятия линейный оператор и матрица эквивалентны.

Рассмотрим самосопряженный положительный линейный оператор = * > 0.Определение. Линейный оператор называется положительным (неотрицательным),если (, ) > 0 ∀ ∈ , ̸= (соответственно (, ) > 0 ∀ ∈ ).Определение. Скалярным произведением в смысле оператора называется скалярноепроизведение, определяемое соотношением(, ) = (, ).§6. Теоремы о сходимости итерационных методов23Определение. Энергетической нормой, порождаемой линейным самосопряженным положительно определенным оператором , называется норма, задаваемая соотношением‖‖ =√︀√︀(, ) = (, ).Задача.

Пусть = * > 0. Доказать, что ∃ > 0 : (, ) > (, ) = ‖‖2 .Рассмотрим свойства положительного самосопряженного линейного оператора.Если = * > 0, то определены матрицы(︁)︁*(︁ 1 )︁*(︁)︁111 *−1 = −1 > 0, 2 = 2 > 0, − 2 = − 2 > 0.Определение. Погрешностью итерационного метода на -ой итерации называетсявектор = − .(3)Определение. Итерационный метод сходится в норме ‖·‖, если ‖ ‖ → 0 при → ∞.Выразим из формулы (3) и подставим в уравнение (2).

Получим однородное уравнение: +1 − + = 0,(4)где ∈ Z+ , 0 = 0 − .Приступим к исследованию задачи (4). Выразим ( + 1)-ую итерацию через -ую с учетом того, что для матрицы существует обратная. Домножим уравнение (4) на −1 слева: +1 − + −1 = 0.Выразим из уравнения погрешность на ( + 1)-ой итерации: +1 = − −1 = ( − −1 ) = .Таким образом, мы получили матрицу , которая связывает предыдущую итерацию с последующей: = − −1 .(5)Определение.

Матрица из уравнения (5) называется матрицей перехода от -ой итерации к ( + 1)-ой.Теорема 1. Итерационный метод (2) решения системы (1) сходится при любом начальном приближении тогда и только тогда, когда все собственные значения матрицыперехода по модулю меньше единицы. (Без доказательства).Таким образом, сходимость итерационного метода (2) всецело зависит от свойств матрицы S, а именно, от ее спектра.Заметим, что данная теорема практически неприменима, так как задача нахожденияполного спектра матрицы аналитически решается крайне редко.Приступим к рассмотрению вопроса сходимости итерационного метода. В дальнейшембудем считать, что линейное пространство задано над полем R вещественных чисел.24Глава 1.

Численные методы линейной алгебрыТеорема 2 (теорема Самарского). Пусть — самосопряженный положительно определенный оператор, — положительное вещественное число и выполнено матричное неравенство − > 0.(6)2Тогда итерационный метод (2) решения системы (1) сходится в среднеквадратичнойнорме при любом начальном приближении:⎯⎸∑︁)︁2⎸ (︁ ‖ − ‖ = ⎷ − −→ 0,=1→∞∀0 .Доказательство.

Введем числовую последовательность = ( , ) > 0. Покажем, что{ } — невозрастающая и ограниченная снизу последовательность. Для этого рассмотрим+1 :+1 = ( +1 , +1 ) = ( , ) = (( − −1 ) , ( − −1 ) ).(7)Воспользуемся линейностью скалярного произведения и преобразуем правую часть равенства:( , ) − ( , −1 ) − ( −1 , ) + 2 ( −1 , −1 ).(8)В силу того, что оператор — самосопряженный ( = * ), получим(︀)︀ (︀)︀ (︀)︀ −1 , = −1 , * = , −1 .Преобразуем выражение (8):)︁(︁(︁(︀)︀ )︁ − 2( , −1 ) + 2 ( −1 , −1 ) = − 2 − −1 , −1 .2Подставив полученное выражение в равенство (7), получим тождество(︁(︁+1 − )︁ −1 −1 )︁(9)+ 2 − , = 0,2(︀)︀в котором оператор − 2 положителен по условию.

Следовательно, второе слагаемоетождества неотрицательно.Отсюда следует, что +1 6 , что и означает монотонностьпоследовательности { }.У невозрастающей последовательности { }, все члены которой неотрицательны, потеореме Вейерштрасса существует предел :lim = .→∞Для дальнейшего доказательства нам понадобится свойство положительно определенного линейного оператора, которое мы сформулируем в виде задачи.Задача. Пусть — вещественное линейное пространство, — положительный линейный оператор в . Доказать, что∃ > 0 : (, ) > ‖‖2 , ∀ ∈ .(10)§6.

Теоремы о сходимости итерационных методов25Воспользуемся свойством (10): существует константа > 0 такая, что(︁(︁)︁ )︁ − −1 , −1 > ‖ −1 ‖2 > 0.2(11)Введем вектор : = −1 .(12)Устремим к бесконечности в равенстве (9):)︁(︁(︁− )︁+ 2 lim − , = 0.→∞2Устремим теперь к бесконечности в неравенстве (11) и примем во внимание полученноеравенство:0 6 lim ‖ ‖2 6 0.→∞Получим, чтоlim ‖ ‖ = 0.→∞Выразим погрешность на -ой итерации из уравнения (12): = −1 .Так как норма произведения операторов не превосходит произведения их норм, а матрица−1 не зависит от номера итерации, то получим, что погрешность стремится к нулюпри , стремящемся к бесконечности:‖ ‖ 6 ‖−1 ‖‖ ‖ −→ 0.→∞Следовательно,lim ‖ ‖ = lim ‖ − ‖ = 0.→∞→∞Так как в ходе доказательства мы не использовали начальное приближение, то ономожет быть произвольным.Следствие 1. Пусть = * > 0.

Тогда метод Якоби сходится в среднеквадратичнойнорме при любом начальном приближении, если выполнено неравенство:2 > ,где = 1 + + 2 , = diag(11 , 22 , . . . , ).Доказательство. В методе Якоби = 1, а = . По теореме Самарского метод сходится,если − > 0.2В нашем случае1 − > 0,2а это выполняется в силу условия 2 > . Следовательно, метод Якоби сходится в среднеквадратичной норме при любом начальном приближении.26Глава 1. Численные методы линейной алгебрыСледствие 2.

Пусть самосопряженная положительно определенная матрица = * >0 является матрицей со строгим диагональным преобладанием:∑︁ >| |, = 1, .=1,̸=Тогда метод Якоби сходится в среднеквадратичной норме при любом начальном приближении 0 .Доказательство. Рассмотрим квадратичную форму с матрицей :(, ) =∑︁ 6,=1∑︁| | | | | |.Для дальнейшей оценки квадратичной формы (13) воспользуемся неравенством 6(, ) 6(13),=12 +22 :1 ∑︁1 ∑︁| | | |2 +| | | |222,=1,=1Преобразуем правую часть неравенства с учетом того, что матрица является самосопряженной (| | = | |):∑︁1 ∑︁1 ∑︁| | | |2 +| | | |2 =| | | |2 .22,=1,=1,=1Вынесем суммирование по индексу и воспользуемся свойством диагонального преобладания матрицы :⎛⎞∑︁∑︁∑︁| |2 ⎝ +| |⎠ <22 = (2, ),=1=1,̸==1где = diag(11 , 22 , . . .

Характеристики

Список файлов лекций