Численные методы. Ионкин (2013) (1160444), страница 2
Текст из файла (страница 2)
. , ) .Так как матрица невырождена, то решение системы (1) существует и единственно. Существуют две группы методов решения СЛАУ:1. Прямые методы (методы Гаусса, Крамера, Холецкого и другие), позволяющие за конечное количество действий получить решение задачи. Эффективность методов этойгруппы оценивается по необходимому количеству умножений и делений.
Несмотря нато, что эти методы часто называют точными, прямые методы таковыми не являютсяиз-за ошибок округления при вычислении.2. Итерационные методы (методы Якоби, Зейделя, Самарского и другие), в которыхзадается начальное приближение 0 и итерационный процесс, по которому строится — последовательность приближений, такая, что ‖ − ‖ < ( > 0 — точностьприближения).Эффективность итерационного метода определяется числом итераций 0 = 0 (),необходимых для получения решения с заданной точностью .Поиск собственных значений матрицыЗадача нахождения собственных значений матрицы (×) состоит в решении уравнения = , ̸= .(2)Здесь — собственное значение, — собственный вектор.
Собственные значения находятсяиз уравнения | − | = 0, которое в общем случае представляет из себя многочлен степени . Однако, как было доказано Абелем и Галуа, при > 5 данное уравнение не имеетобщего решения в радикалах. Таким образом, в общем виде задачу можно решить тольковычислительными методами.§2. Связь метода Гаусса с факторизацией матрицы9Рассматривают две проблемы поиска собственных значений:1.
Частичная проблема собственных значений — нахождение отдельных собственных значений (например, максимального и минимального по модулю).2. Полная проблема собственных значений (для решения обычно используется метод–разложения матрицы ) — нахождение спектра (всех собственных значений) матрицы.Нахождение обратной матрицыОпределение. Матрица −1 называется обратной к матрице , если она удовлетворяет равенствам−1 = −1 = .Как мы помним из курса линейной алгебры, если нам известна матрица, обратная к матрице , например, в задаче поиска решения системы линейных уравнений (1), то решениенаходится очень просто: = −1 .
В дальнейшем мы будем активно использовать понятиеобратной матрицы не только в контексте прямого поиска решения, но и при исследованиина сходимость численных методов нахождения решений различных задач и оценке скоростиих сходимости.§2Связь метода Гаусса с факторизацией матрицыРассмотрим матричное уравнение вида = ,(1)где || ̸= 0, ( × ), = (1 , 2 , . . . , ) , = (1 , 2 , . .
. , ) . Матрица , вообщеговоря, может быть матрицей с комплексными элементами.Рассмотрим факторизацию (разложение в произведение) матрицы ( × ) = · ,(2)где — нижнетреугольная матрица, а — верхнетреугольная матрица с единицами на главной диагонали:⎛⎞⎛⎞110 ···01 12 · · · 1⎜ 21 22 · · ·⎜0 1 · · · 2 ⎟0 ⎟⎜⎟⎜⎟=⎜ .,=⎟⎜ ........ . ... ⎟ ...⎝ ..⎠⎝....... ⎠1 2 · · · 00···1Ясно, что не любую матрицу можно представить в виде (2). В дальнейшем мы покажем,что нахождение элементов матриц и возможно при определенном ограничении наматрицу . Запишем определение элемента матрицы через произведение -ой строкиматрицы и -ого столбца матрицы : =∑︁ .=1Выделим -ое слагаемое: =−1∑︁=1 + +∑︁=+1 .10Глава 1. Численные методы линейной алгебрыУчитывая структуру матрицы ( = 0, > , = 1), получим = −−1∑︁ , > .(3)=1Аналогично, в определении элемента матрицы выделим -ое слагаемое: =−1∑︁ + +=1∑︁ .=+1Исходя из вида матрицы ( = 0, > ), получим = −−1∑︁ .=1Предполагая, что ̸= 0, поделим левую и правую части уравнения на : − =−1∑︀ =1, < .(4)Несмотря на то, что уравнения (3) и (4) образуют нелинейную систему уравнений, элементыматриц и можно вычислить по явным формулам.
Приведем алгоритм нахожденияэлементов матриц и .1. 11 = 11 . Найдем элементы 1-й строки матрицы :1 =1,11 = 2, .2. Рассмотрим элементы 1-ого столбца матрицы :1 = 1 , = 2, .3. 22 = 22 − 21 12 . Далее, аналогично 1-ому шагу, найдем элементы 2-ой строки матрицы :2 − 21 12 =, = 3, .224. Вычислим элементы 2-ого столбца матрицы аналогично 2-ому шагу:2 = 2 − 1 12 , = 3, .5. Повторяя последовательно шаги алгоритма для столбцов матрицы и строк матрицы, найдем все элементы матриц и .Утверждение. Пусть все угловые миноры матрицы отличны от нуля.
Тогда представление матрицы в виде (2) существует и единственно.⃒⃒⃒11 . . . 1 ⃒⃒⃒⃒⃒⃒11 12 ⃒⃒ ..⃒..⃒⃒.., . . . , = ⃒ .Доказательство. Обозначим |1 | = 11 ̸= 0, 2 = ⃒. . ⃒⃒ , = 1, .21 22 ⃒⃒⃒ 1 . . . ⃒Поскольку | | ≠ 0, введем для определенности |0 | = 1. = · , = 1, .§2. Связь метода Гаусса с факторизацией матрицы11Подсчитаем значение определителя матрицы , приняв во внимание вид матриц и и равенство | | = 1:| | = | || | = 11 22 · . .
. · −1,−1 ,⏟⏞|−1 | =| |̸= 0,|−1 | = 1, .Подставив в формулы (3) и (4), получим факторизацию матрицы . Следовательно,факторизация матрицы в виде (2) существует и определяется единственным образом.Задача. Показать, что для вычисления элементов матриц и по формулам (3) и (4)3требуется 3− умножений и делений.Решение. Оценим необходимое количество операций для вычисления элементов поформуле (3).
Для вычисления фиксированного потребуется ( − 1) умножение. Зафиксировав и учитывая, что > , получим∑︁( − 1) ==1( − 1).2Далее, варьируя от 1 до , получим(︃ )︃(︂)︂∑︁1 ∑︁ 2 ∑︁1 ( + 1)(2 + 1) ( + 1)( − 1)( + 1)( − 1)=−=. − =222626=1=1=1Оценим необходимое количество операций для вычисления элементов по формуле (4). Для вычисления фиксированного потребуется ( − 1) умножение и одно деление.При фиксированном получим−1∑︁( − 1)=.2=1Далее, варьируя от 1 до , получим аналогичную формулу:∑︁( − 1)=12=( − 1)( + 1).6Сложив необходимое количество операций для вычисления и , получим искомыйрезультат:( − 1)( + 1) ( − 1)( + 1)3 − +=.663Замечание. Классическим методом решения СЛАУ вида (1) является метод Гаусса.Кратко вспомним, в чем он заключается:1.
Прямой ход. С помощью элементарных преобразований матрица [| ], получаемаяприписыванием к матрице вектор-столбца правых частей системы уравнений (1), приводится к матрице [′ | ′ ], где ′ — верхнетреугольная матрица с единицами на главной диагонали:[| ] → . . . → [′ | ′ ].12Глава 1. Численные методы линейной алгебрыНа этом этапе мы получили новую СЛАУ′ = ′ ,(5)эквивалентную данной: ее решение совпадает с решением исходной задачи.2. Обратный ход метода Гаусса. Последовательно, начиная с последнего уравненияСЛАУ (5) и поднимаясь к первому, по явным формулам вычисляются все компоненты решения системы.Число действий, необходимое для преобразований матрицы в прямом ходе метода Гаусса3равно 3− .
Подробный подсчет числа действий можно найти, например, в [8]. Заметим, что матрица ′ , к которой приводится матрица в прямом ходе метода Гаусса,в точности совпадает с матрицей , полученной в результате факторизации матрицы в виде (2). Таким образом факторизация матрицы в виде (2) требует такое жечисло действий, что и сведение матрицы к ′ в прямом ходе метода Гаусса.В матричном уравнении (1) подставим = : = , обозначим = и получимдве системы уравнений с треугольными матрицами:{︂ = (6) = (1 , . . . , ) . = ,(7)Запишем -ое уравнение системы (6):1 1 + 2 2 + . . . + = , = 1, .Предполагая, что ̸= 0, получим − =−1∑︀ =1.Для вычисления требуется ( − 1) умножение и 1 деление — всего операций.
Учитывая,что изменяется от 1 до , получим, что для решения системы (6) требуется 1+2+. . .+ =(+1)операций.2Замечание 1. На вычисление новых правых частей, т.е. вектора ′ , в методе Гауссауходит (+1)действий. Как мы можем видеть, это число совпадает с количеством2операций, необходимых для вычисления вектора y при решении системы (6).Аналогично, запишем -ое уравнение системы (7): + ,+1 +1 + . .
. + = , = −∑︁ , = 1, .=+1Для вычисления требуется ( − ) умножений. Изменяя от 1 до , получим, что длярешения системы (7) требуется ( − 1) + ( − 2) + . . . + 2 + 1 = (−1)умножений.2Замечание 2. Число операций, затрачиваемых на выполнение обратного хода методаГаусса, равно (−1), что совпадает с числом действий, требуемых для решения систе2мы (7).§3. Обращение матрицы методом Гаусса-Жордана13В итоге получим, что для решения систем (6) и (7) требуется (−1)+ (+1)= 222операций. Тогда все решение системы (1) с использованием факторизации матриц требует32 −3 −+ 2 = +3операций, что равно общему числу операций, необходимых для33решения этой же системы методом Гаусса.
Таким образом, решение системы (1) методомГаусса эквивалентно по числу операций факторизации матрицы и решению двух системуравнений.Замечание 3. Возникает вопрос о необходимости решения СЛАУ (1) именно с использованием факторизации вместо классического метода Гаусса. Выигрыш по числу операцийобусловлен особенностями задач, встречающихся на практике: как правило, решаютсяцелые серии задач с одной и той же матрицей , которая описывает математическуюмодель изучаемого объекта или процесса, и с различными правыми частями , которыесоответствуют изменяющимся входным условиям. Таким образом, можно один раз факторизовать матрицу , а затем для нахождения решения каждой задачи решать лишьСЛАУ вида (6) и (7) для каждого наблюдения.§3Обращение матрицы методом Гаусса-ЖорданаРассмотрим задачу обращения (поиска обратной матрицы) невырожденной матрицы (×).
Согласно критерию обратимости матрицы, для невырожденной матрицы всегда существует обратная. Введем обозначение: −1 = = ( ), , = 1, . С учетом этого задачаобращения матрицы состоит в решении системы = ,(1)где ( × ), || ≠ 0, или, если записать поэлементно:∑︁ = .(2)=1Можно приступить к решению последней системы методом Гаусса без учета структурыматрицы коэффициентов. Эта система имеет 2 неизвестных переменных, число требуемых для решения операций будет пропорционально 6 .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
