Численные методы. Ионкин (2013) (1160444), страница 3
Текст из файла (страница 3)
Покажем, что существует способобращения матрицы, требующий ровно 3 операций. Более того, в случае, если матрица имеет специальную структуру (например, если матрица — блочная или трехдиагональная), число операций уменьшится.Сведем уравнение (2) к решению систем линейных уравнений с матрицей . Для этоговведем вектор-столбец матрицы : () = (1 , 2 , . . . , ) и вектор-столбец правойчасти () = (0, 0, . .
. , 0, 1, 0, . . . , 0) с единицей на -ой позиции. Теперь можем записатьматричное уравнение (1) в виде систем: () = () , = 1, .(3)Факторизуем матрицу в виде = · .Для этого требуетсянений:3 −3(4)умножений и делений. Получаем две системы линейных урав{︃ () = ()()=()(5).(6)14Глава 1.
Численные методы линейной алгебрыПри фиксированном решение систем (5) и (6) требует число действий, равное 2 . Для решения таких систем при = 1, потребуется 3 действий. Значит, в целом3для обращения матрицы необходимо 3 + 3− ∼ 34 3 операций. Покажем теперь, чтоэто число операций можно уменьшить. Рассмотрим систему уравнений (5):11 1 = 0()⇒1 = 0,()()⇒2 = 0,()()⇒3 = 0,21 1 + 22 2 = 0()31 1 + 32 2 + 33 3 = 0()()()...()()()⇒ −1 = 0.−1,1 1 + . . . + −1,−1 −1 = 0()= 1.
Предполагая, что ̸= 0, получим:Рассмотрим -ое уравнение: ()=1.(7)Запишем уравнения системы при > ()()() + ,+1 +1 + . . . + = 0, = ( + 1), ,(8)()и выразим из них :−()−1∑︀=() , = ( + 1), .(9)Перейдем к подсчету числа операций, необходимых для решения систем уравнений (5) и (6).При фиксированных и в формуле (9) получаем ( − ) умножений и одно деление ив уравнении (7) одно деление. Варьируя индекс от 1 до , при фиксированном получаем=( − )( − + 1)2умножений и (− +1) делений. Таким образом, число действий, необходимое для решенияодной системы (5) равно( − ) + ( − − 1) + . .
. + 1 =( − )( − + 1) 2( − + 1)( − + 1)( − + 2)+=.222Общее число действий, необходимое для решения всех систем (5) равно∑︁( − + 1)( − + 2)2=1Задача. Показать, что сумма (10) равна.(10)(+1)(+2).6Решение. Сделаем замену = − + 1 в формуле (10):∑︁( − + 1)( − + 2)=12=∑︁( + 1)=12.Преобразовав полученное выражение, получим искомый результат:(︃ )︃(︂)︂1 ∑︁ 2 ∑︁1 ( + 1)(2 + 1) ( + 1)( + 1)( + 2) + =+=.22626=1=1§4. Метод квадратного корня152.Аналогично получаем, что число операций для решения всех систем вида (6) равно (−1)2Просуммируем число операций для факторизации исходной матрицы и для решения систем (5) и (6) при = 1, :3 − ( + 1)( + 2) 2 ( − 1)++= 3 .362Описанный выше метод обращения произвольной невырожденной матрицы называетсяметодом Гаусса-Жордана.
Отметим, что он является самым эффективным методом обращения невырожденных матриц произвольного вида.§4Метод квадратного корняОпределение. Квадратная матрица называется эрмитовой (самосопряженной), если = * (ее элементы связаны соотношением = ).Рассмотрим задачу = ,(1)где ∈ C× , = * , || ≠ 0, = (1 , 2 , . .
. , ) , = (1 , 2 , . . . , ) , и одиниз прямых методов ее решения — метод квадратного корня (метод Холецкого).Заметим, что хотя класс эрмитовых матриц с точки зрения линейной алгебры достаточно узок, на практике часто возникают модели, описываемые именно этим классом матриц.Поэтому с практической точки зрения такое ограничение на систему (1) вполне допустимо.Факторизуем эрмитову матрицу в виде = * ,(2)где матрица — верхнетреугольная матрица с положительными элементами на главнойдиагонали, а — диагональная матрица со значениями ±1 на главной диагонали:⎛⎞⎛⎞11 12 · · · 111 0 · · ·0⎜ 0 22 · · · 2 ⎟⎜ 0 22 · · ·0 ⎟⎜⎟⎜⎟=⎜ .,>0,=⎟⎜.. .
......... ⎟ , = ±1...⎝ ..⎠⎝....... ⎠00· · · 00· · · Покажем, что факторизация (2) возможна на примере вещественной симметрическойматрицы второго порядка:(︂)︂11 12== , 12 = 21 .21 22Матрицы и будем искать в виде(︂)︂11 12=, > 0, = 1, 2,0 22(︂)︂11 0 = =,12 22(︂)︂11 0=, = ±1, = 1, 2.0 22*16Глава 1. Численные методы линейной алгебрыНайдем матрицу :(︂ =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Выделим -ое слагаемое из последней суммы и учтем, что ( * ) = : =−1∑︁=1 + +∑︁=+1 ,, = 1, .§4.
Метод квадратного корня17Третье слагаемое из равенства равно нулю в силу того, что матрица * является нижнетреугольной: = 0, > . Тогда получим: =−1∑︁ + ,, = 1, .(6)=1Так как матрица эрмитова, можем рассматривать это равенство только в случае 6 .При = получим:−1∑︁ = + , = 1, .=1Учтем, что = | |2 : =−1∑︁ | |2 + | |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. Численные методы линейной алгебрыПримеры и канонический вид итерационных методов решения СЛАУРассмотрим матричное уравнение = ,(1)где || ≠ 0, ( × ), = (1 , 2 , . . . , ) , = (1 , 2 , . . .
, ) .Распишем систему (1) покоординатно:∑︁ = , = 1, .(2)=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.. .⎠.......... ⎠⎝ ..⎝ ..⎝.. .....
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
