Численные методы. Ионкин (методичка) (2015) (1160451), страница 3
Текст из файла (страница 3)
Для этоговведем вектор-столбец матрицы : () = (1 , 2 , . . . , ) и вектор-столбец правойчасти () = (0, 0, . . . , 0, 1, 0, . . . , 0) с единицей на -й позиции. Теперь можем записатьматричное уравнение (1) в виде систем: () = () , = 1, .(3)14Факторизуем матрицу в виде(4) = · .Для этого требуетсянений:3 −3умножений и делений. Получаем две системы линейных урав-{︃ () = () ,()=()(5) = 1, ,(6).При фиксированном решение систем (5) и (6) потребует 2 действий. Для решения таких систем при = 1, потребуется 3 действий. Значит, в целом для обращения3матрицы необходимо 3 + 3− ∼ 43 3 операций. Покажем теперь, что это числоопераций можно уменьшить.
Рассмотрим систему уравнений (5):11 1 = 0()⇒1 = 0,()()⇒2 = 0,()()⇒3 = 0,21 1 + 22 2 = 0()31 1 + 32 2 + 33 3 = 0()()()...()()−1,1 1 + . . . + −1,−1 −1 = 0()Рассмотрим -ое уравнение: ()⇒ −1 = 0.= 1. Предполагая, что ̸= 0, получим:()=1.(7)Запишем уравнения системы при > ()()() + ,+1 +1 + . . . + = 0, = ( + 1), ,(8)()и выразим из них :−()=−1∑︀=() = ( + 1), .,(9)Перейдем к подсчету числа операций, необходимых для решения систем уравнений (5) и (6).При фиксированных и в формуле (9) получаем ( − ) умножений и одно деление в уравнении (7). Варьируя индекс от 1 до , при фиксированном получаем( − ) + ( − − 1) + . . .
+ 1 =( − )( − + 1)2умножений и (− +1) делений. Таким образом, число действий, необходимое для решенияодной системы (5) равно( − + 1)( − + 2)( − )( − + 1) 2( − + 1)+=.222Общее число действий, необходимое для решения всех систем (5) равно∑︁( − + 1)( − + 2)=12.(10)§4. Метод квадратного корняЗадача.15Показать, что сумма (10) равнаРешение.(+1)(+2).6Сделаем замену = − + 1 в формуле (10):∑︁( − + 1)( − + 2)=12=∑︁( + 1)2=1.Преобразовав полученное выражение, получим искомый результат:(︃ )︃(︂)︂( + 1)( + 2)1 ∑︁ 2 ∑︁1 ( + 1)(2 + 1) ( + 1)= ++. =22626=1=1Аналогично получаем, что число операций для решения всех систем вида (6) равно2 (−1). Просуммируем число операций для факторизации исходной матрицы и для реше2ния систем (5) и (6) при = 1, :3 − ( + 1)( + 2) 2 ( − 1)++= 3 .362Описанный выше метод обращения произвольной невырожденной матрицы называетсяметодом Гаусса-Жордана.
Отметим, что он является самым эффективным методом обращения невырожденных матриц произвольного вида.§4Метод квадратного корняОпределение. Квадратная матрица называется эрмитовой (самосопряженной), еслиее элементы связаны соотношением = ). В этом случае будем записывать = * .Рассмотрим задачу(1) = ,где ∈ C× , = * , || ≠ 0, = (1 , 2 , .
. . , ) , = (1 , 2 , . . . , ) , и одиниз прямых методов ее решения — метод квадратного корня (метод Холецкого).Заметим, что хотя класс эрмитовых матриц с точки зрения линейной алгебры достаточно узок, на практике часто возникают модели, описываемые именно этим классом матриц.Поэтому с практической точки зрения такое ограничение на систему (1) вполне допустимо.Факторизуем эрмитову матрицу в виде = * ,(2)где матрица — верхнетреугольная матрица с положительными элементами на главнойдиагонали, а — диагональная матрица со значениями ±1 на главной диагонали:⎛⎞⎛⎞11 0 · · ·011 12 · · · 1⎜ 0 22 · · · 2 ⎟⎜ 0 22 · · ·0 ⎟⎜⎟⎜⎟=⎜ ., > 0,=⎜ .⎟.....
⎟ , = ±1..........⎝ .⎝ ..... ⎠.. ⎠00· · · 00· · · Покажем, что факторизация (2) возможна на примере вещественной симметрическойматрицы второго порядка. Не ограничивая общности, будем полагать 11 ̸= 0.(︂)︂11 12== , 12 = 21 .21 2216Матрицы и будем искать в виде(︂)︂11 12=, > 0, = 1, 2,0 22(︂)︂11 0* = =,12 22(︂)︂11 0=, = ±1, = 1, 2.0 22Найдем матрицу :(︂ =11 00 22)︂ (︂)︂(︂)︂11 1211 11 11 12=.0 22022 22Домножим матрицу слева на :(︂)︂ (︂)︂(︂11 011 11 11 1211 211 ==12 22022 2211 11 12)︂11 11 12.11 212 + 22 222Приравняем элементы матриц и :⎧2⎪⎨ 11 = 11 1112 = 11 11 12⎪⎩22 = 11 212 + 22 222 .(3)(4)(5)Из неравенства 11 > 0 и из уравнения (3) следует, что√︀11 = sgn 11 , 11 = |11 |.Рассмотрим уравнение (4). Заметим, что 11 11 ̸= 0, тогда12 =12.11 11Наконец, рассмотрим уравнение (5).
Получим соотношение 222 22 = 22 − 11 212 , праваячасть которого известна. Следовательно,√︁22 = sgn(22 − 212 11 ), 22 = |22 − 212 11 |.Таким образом, вещественную симметрическую матрицу второго порядка можно факторизовать в виде (2).Рассмотрим теперь произвольную эрмитову матрицу ( × ). Запишем уравнениедля элементов матрицы :() =∑︁ ,, = 1, .=1Учитывая диагональную структуру матрицы , получим:() = .Домножим матрицу слева на * : = ( * ) =∑︁=1( * ) ,, = 1, .§4. Метод квадратного корня17Выделим -ое слагаемое из последней суммы и учтем, что ( * ) = : =−1∑︁ + +=1∑︁ ,, = 1, .=+1Третье слагаемое из равенства равно нулю в силу того, что матрица * является нижнетреугольной: = 0, > . Тогда получим: =−1∑︁ + ,, = 1, .(6)=1Так как матрица эрмитова, достаточно рассматривать это равенство только в случае 6 .
При = получим: =−1∑︁ + , = 1, . | |2 + | |2 , = 1, ,=1Учтем, что = | |2 : =−1∑︁=1 | |2 = −−1∑︁| |2 , = 1, .| |2 ), = 1, ,(7)⎯⃒⃒⎸⃒−1⃒∑︁⎸⃒⃒ = ⎷⃒ −| |2 ⃒,⃒⃒ = 1, .(8)=1Выразим и : = sgn( −−1∑︁=1=1Рассмотрим случай ̸= ( < ). В уравнении (6) выделим второе слагаемое: = −−1∑︁ ,, = 1, .=1В силу того, что — вещественные положительные числа, получим = −−1∑︁ ,, = 1, .=1Так как ̸= 0, то получим выражения для коэффициентов : − =−1∑︀ =1 ,, = 1, , < .(9)Таким образом, для вычисления элементов матриц в разложении (2) были получены явныеформулы (7) – (9).Метод квадратного корня позволяет примерно вдвое уменьшить число операций, необ3ходимых для решения системы (1), по сравнению с методом Гаусса — до ∼ 6 умножений иделений.
Кроме этого необходимо операций извлечения квадратного корня. Заметим, чтометод справедлив только в случае, если матрица системы линейных уравнений эрмитова.18§5Примеры и канонический вид итерационных методов решения СЛАУРассмотрим матричное уравнение(1) = ,где || ≠ 0, ( × ), = (1 , 2 , . . . , ) , = (1 , 2 , . .
. , ) .Распишем систему (1) покоординатно:∑︁(2) = 1, . = ,=1Выделим -ое слагаемое в сумме:−1∑︁∑︁ + +=1 = , = 1, .=+1Предположим, что элементы главной диагонали матрицы отличны от нуля: ̸= 0, =1, . Тогда уравнение (2) разрешимо относительно : −−1∑︀=1 =∑︀ − =+1, = 1, .Все итерационные методы основаны на построении последовательности векторов =(1 , . . .
, ) такой, что → при → ∞, где — точное решение матричного уравнения (1). Вектор называется -й итерацией метода.Отметим, что при выборе итерационного метода важно, чтобы метод был легко реализуем и сходился к решению достаточно быстро.Итерационный метод называется двухслойным, если для вычисления текущей итерации используются только элементы предыдущей итерации.Определение.Замечание.Двухслойный итерационный метод также называют одношаговым.Для того, чтобы начать процесс построения последовательности , необходимо задатьначальное приближение 0 . Далее будем предполагать, что начальное приближение ужезадано.Рассмотрим в качестве примера два простейших двухслойных итерационных метода:метод Якоби и метод Зейделя.Метод ЯкобиМетод Якоби является явным итерационным методом и задается правилом −+1=−1∑︀=1 −∑︀=+1 , = 1, , ∈ Z+ .Забегая вперед, заметим, что метод Якоби является легко реализуемым, но при этом медленно сходящимся, особенно при больших .§5.
Примеры и канонический вид итерационных методов решения СЛАУ19Метод ЗейделяМетод Зейделя, в отличие от метода Якоби, является неявным итерационным методом изадается уравнением −+1=−1∑︀=1 +1 −∑︀=+1 = 1, , ∈ Z+ .,В правой части уравнения используются координаты ( + 1)-й итерации, поэтому методЗейделя является неявным. Но если разумно организовать вычисления, то можно найтикоординаты ( + 1)-й итерации по явным формулам.Рассмотрим метод Зейделя при = 1:1 −∑︀=2+1=11 ,11 ∈ Z+ .Видно, что +1находится по явной формуле. Рассмотрим вторую координату ( + 1)-й1итерации:∑︀−2 2 − 21 +11=3+1=222, ∈ Z+ .можно найти по явной формуле.известна, то координату +1Так как координата +121Продолжая вычисления, получим, что каждый элемент ( + 1)-й итерации можно найти по явным формулам от уже известных элементов.
Заметим, что метод Зейделя проств реализации, но медленно сходится.Каноническая запись итерационных методовДля исследования сходимости итерационных методов удобно записывать их в матричномвиде. Представим матрицу в виде = 1 + + 2 ,где 1 — нижнетреугольная матрица с нулевой главной диагональю, — диагональнаяматрица, 2 — верхнетреугольная матрица с нулевой главной диагональю:⎛⎞⎛⎞⎛⎞0 12 · · · 100 ··· 011 0 · · ·0⎜ 21⎜ 0 22 · · ·⎜0 0 · · · 2 ⎟0 · · · 0⎟0 ⎟⎜⎟⎜⎟⎜⎟1 = ⎜ .,=,=⎟⎜⎟⎜ ........... ⎟ .2..
.⎠.......... ⎠⎝ ..⎝ ..⎝.. ..... ⎠1 2 · · · 000· · · 00···0Перепишем матричное уравнение (1) в виде(1 + + 2 ) = .Оставим в левой части слагаемое с матрицей , остальные слагаемые перенесем в правуючасть уравнения: = − 1 − 2 .Предположим, что матрица обратима ( ̸= 0, = 1, ). Тогда получим: = −1 − −1 1 − −1 2 .(3)20Запишем итерационные методы Якоби и Зейделя исходя из уравнения (3):Метод Якоби :Метод Зейделя :+1 = −1 − −1 1 − −1 2 , ∈ Z+ ,+1 = −1 − −1 1 +1 − −1 2 , ∈ Z+ .Рассмотрим эти два метода записав их в виде:Метод Якоби :+1 + (1 + 2 ) = , ∈ Z+ ,Метод Зейделя :( + 1 )+1 + 2 = , ∈ Z+ .Наконец, перепишем эти соотношения в видеМетод Якоби :Метод Зейделя : ∈ Z+ ,(4)− ) + = , ∈ Z+ .(5)(+1 − ) + = ,( + 1 )(+1Из формул (4) и (5) видно, что если в каждом из методов последовательность итерацийсходится, то она сходится к решению системы (1).Мы видим, что один и тот же итерационный метод можно записать различными способами.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
