Н.И. Ионкин - Численные методы, страница 3

. . → [′ | ′ ].На этом этапе мы получили новую СЛАУ′ = ′ ,(5)эквивалентную данной: ее решение совпадает с решением исходной задачи.2. Обратный ход метода Гаусса. Последовательно, начиная с последнего уравнения СЛАУ (5) и поднимаясь к первому, по явным формуламвычисляются все компоненты решения системы.Число действий, необходимое для преобразований матрицы в прямом хо3де метода Гаусса равно 3− . Подробный подсчет числа действий можнонайти, например, в [8] c. 13.

Заметим, что матрица ′ , к которой приводится матрица в прямом ходе метода Гаусса, в точности совпадаетс матрицей , полученной в результате факторизации матрицы в виде (2). Таким образом факторизация матрицы в виде (2) требует такоеже число действий, что и сведение матрицы к ′ в прямом ходе методаГаусса.§2. Связь метода Гаусса с факторизацией матрицы17В матричном уравнении (1) подставим = : = , обозначим = и получим две системы уравнений с треугольными матрицами:{︂ = (6) = (1 , . . .

, ) . = ,(7)Запишем -ое уравнение системы (6):1 1 + 2 2 + . . . + = , = 1, .Предполагая, что ̸= 0, получим − =−1∑︀ =1.Для вычисления требуется (−1) умножение и 1 деление — всего операций.Учитывая, что изменяется от 1 до , получим, что для решения системы (6)операций.требуется 1 + 2 + . . . + = (+1)2На вычисление новых правых частей, т.е. вектора ′ , в методе Гаусса уходит (+1)действий. Как мы можем видеть, это число2совпадает с числом операций, необходимых для вычисления вектора y прирешении системы (6).Замечание 1.Аналогично, запишем -ое уравнение системы (7): + ,+1 +1 + .

. . + = , = −∑︁ , = 1, .=+1Для вычисления требуется ( − ) умножений. Изменяя от 1 до , получим, что для решения системы (7) требуется ( − 1) + ( − 2) + . . . + 2 + 1 =(−1)умножений.2Число операций, затрачиваемых на выполнение обратногохода метода Гаусса, равно (−1), что совпадает с числом действий, тре2буемых для решения системы (7).Замечание 2.В итоге получим, что для решения систем (6) и (7) требуется (−1)+2(+1)2= операций. Тогда все решение системы (1) с использованием2332 −факторизации матриц требует 3− + 2 = +3операций, что равно3общему числу операций, необходимых для решения этой же системы методомГаусса. Таким образом, решение системы (1) методом Гаусса эквивалентно почислу операций факторизации матрицы и решению двух систем уравнений.18Глава I . Численные методы линейной алгебрыПоясним, в каких случаях выгодно решать СЛАУ (1) именно с использованием факторизации вместо классического метода Гаусса.На практике: как правило, решаются целые серии задач с одной и той жематрицей , которая описывает математическую модель изучаемого объекта или процесса, и с различными правыми частями , которые соответствуют изменяющимся входным условиям.

Таким образом, можно один разфакторизовать матрицу , а затем для нахождения решения каждой задачи решать лишь СЛАУ вида (6) и (7) для каждого наблюдения. Так какв методе Гаусса наибольшее число действий требуется на преобразование3матрицы к верхнему треугольному виду ( 3− ), то решая серию СЛАУс фиксированной матрицей с использованием факторизации, разложение3 = осуществляется лишь один раз, затрачивая на это 3− действий, а затем решается серия СЛАУ с меняющимися правыми частями.В итоге, общее число операций на решение серии СЛАУ будет меньше, чемпри решении той же серии классическим методом Гаусса.

Этот выигрышбудет виден при решении задачи обращения невырожденной матрицы.Замечание 3.§3Обращение матрицы методом Гаусса-ЖорданаРассмотрим задачу обращения (поиска обратной матрицы) невырожденнойматрицы ( × ). Согласно критерию обратимости матрицы, для невырожденной матрицы всегда существует обратная. Введем обозначение: −1 = = ( ), , = 1, . С учетом этого задача обращения матрицы состоит врешении системы = ,(1)где ( × ), || ≠ 0, или, если записать поэлементно:∑︁ = , = 1, , = 1, .(2)=1Можно приступить к решению последней системы методом Гаусса без учета структуры матрицы коэффициентов.

Эта система имеет 2 неизвестныхпеременных, число требуемых для решения операций будет пропорционально6 . Покажем, что существует способ обращения матрицы, требующий ровно3 операций. Более того, в случае, если матрица имеет специальную структуру (например, если матрица — блочная или трехдиагональная), числоопераций уменьшится.Сведем уравнение (2) к решению систем линейных уравнений с матрицей . Для этого введем вектор-столбец матрицы : () = (1 , 2 , .

. . , )§3. Обращение матрицы методом Гаусса-Жордана19и вектор-столбец правой части () = (0, 0, . . . , 0, 1, 0, . . . , 0) с единицей на й позиции. Теперь можем записать матричное уравнение (1) в виде систем: () = () ,(3) = 1, .Факторизуем матрицу в виде(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)20Глава I . Численные методы линейной алгебрыПерейдем к подсчету числа операций, необходимых для решения систем уравнений (5) и (6). При фиксированных и в формуле (9) получаем ( − )умножений и одно деление в уравнении (7). Варьируя индекс от 1 до , прификсированном получаем( − ) + ( − − 1) + .

. . + 1 =( − )( − + 1)2умножений и (−+1) делений. Таким образом, число действий, необходимоедля решения одной системы (5) равно( − )( − + 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Аналогично получаем, что число операций для решения всех систем вида2.

Просуммируем число операций для факторизации исход(6) равно (−1)2ной матрицы и для решения систем (5) и (6) при = 1, :3 − ( + 1)( + 2) 2 ( − 1)++= 3 .362Описанный выше метод обращения невырожденной матрицы называетсяметодом Гаусса-Жордана. Отметим, что он является самым эффективнымметодом обращения невырожденных матриц.§4.

Метод квадратного корня§421Метод квадратного корняКвадратная матрица называется эрмитовой (самосопряженной), если ее элементы связаны соотношением = ). В этом случаебудем записывать = * .Определение.Рассмотрим задачу(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 ̸= 0.(︂)︂11 12== , 12 = 21 .21 22Матрицы и будем искать в виде(︂)︂11 12=, > 0, = 1, 2,0 22(︂)︂11 0* = =,12 22(︂)︂11 0=, = ±1, = 1, 2.0 2222Глава I . Численные методы линейной алгебрыНайдем матрицу :(︂)︂ (︂)︂(︂)︂11 011 1211 11 11 12 ==.0 220 22022 22Домножим матрицу слева на :(︂)︂ (︂)︂(︂11 011 11 11 1211 211 ==12 22022 2211 11 12)︂11 11 12.11 212 + 22 222Приравняем элементы матриц и :⎧2⎪⎨ 11 = 11 11(3)12 = 11 11 12⎪⎩22 =11 212+22 222 .(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Учитывая диагональную структуру матрицы , получим:() = .§4. Метод квадратного корня23Домножим матрицу слева на * : = ( * ) =∑︁( * ) ,, = 1, .=1Выделим -ое слагаемое из последней суммы и учтем, что ( * ) = : =−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=124Глава I . Численные методы линейной алгебрыРассмотрим случай ̸= ( < ). В уравнении (6) выделим второе слагаемое: = −−1∑︁ ,, = 1, .=1В силу того, что — вещественные положительные числа, получим = −−1∑︁ ,, = 1, .=1Так как ̸= 0, то получим выражения для коэффициентов : − =−1∑︀ =1, , = 1, , < .(9)Таким образом, для вычисления элементов матриц в разложении (2) былиполучены явные формулы (7) – (9).Метод квадратного корня позволяет примерно вдвое уменьшить числоопераций, необходимых для решения системы (1), по сравнению с методом3Гаусса — до ∼ 6 умножений и делений.