Турчак Л.И. Основы численных методов. Под ред. В.В.Щенникова (1987) (1095857), страница 23
Текст из файла (страница 23)
Приближение с номером й можно представить в виде (з). 1 /т,(й — д) (й-д)1 Хд = — ~йд — адзхз — адзхз дд (А) 1 / (й) (й-,д) 1 х, = — (Ьз — а„х, — аззхз 22 ю 1 ~ ао а)~ з = а ~" з — аз,хд — аззхз / 'зз Итерационный процесс продолжается до тех пор, пока () ) (й) () ) значения хд, хз, хз не станут близкими с заданпои „о -д),(й-д) (й-д) погрешностью к значениям х,, хз . Хз Пример. Решить с помощью метода Гаусса — Зей- деля следующую систему уравнений: 4х,— х,+ х,=4, 2Х, +бх,— х, =7, х, + 2Х, — Зхз = О. Легко проверить, что решение данной системы следую- щее: Х,=1, х,-1, х,=1. Ре ш он ие. Выразим неизвестные х„х, и х, соответ- ственно из первого, второго и третьего уравнений: х, = — (4+ х, — х,), х, = —., (7 — 2Х, + хз)1 У 1 в хз = ~ (хд + 2х,).
Б качестве начального приближения (как это обычно делается) примем х, = О, хз = О, хз — — О, Найдем по- (0) (0) (О) вые приближенна неизвестных: =' — (4+ Π— 0) = 1, хз 6 (7 — 2 ° 1+ 0) = (д) (д) 1 5 1.,8 гл. 4. снстемы линейных уРлвнении Аналогично вычислим следующие приближения: г1) 1 ( 5 8~ 71 |2) 1( 71 81 71 х = — ~4 + — ' — — (= —, х. = — ~7 — 2 ° — + — (= —. 4 !, 6 9! 72' 1 6!, 72 9( 72"' |1) 1 (71 71~ 71 3 )» 72 ?2,» 72 ' Итерационный процесс можно продолжать до полученпя малой разности между значениями неизвестных в двух последовательных итерациях.
Рассмотрим теперь систему и линейных уравнений с и неизвестными. Запишем ее в виде а;,х, +... + а;,;,х;, + а„х; + а;;+,х|+, +... + а.;„х = б;, 1=1, 2... и, Здесь также будем предполагать, что все диагональные элементы отличны от нуля. Тогда в соответствии с методом Гаусса — Зейделя й-е приближение к решению можно представить в виде 'и — а;;+,х',",1" —,, » — а;пхи ')» 1 = 4» 2» ° ° . » я. (4.29) Итерационный процесс продолжается до тех пор, пока й) |А — 1) все значения х» ' не станут близкими к х';, Близость этих значений можно характеризовать максимальной абсолютной величиной их разности 6. Тогда при заданной допустимой погрешности е ~ 0 критерий окончания итерационного процесса можно записать в виде о= шах !х;"' — х, "~(е, (4,30) 1 4 1 «4»» Это критерий по абсолютным отклонениям.
Можно заменить его критерием по относительным разностям, т. е, условие окончания итерационного процесса записать в виде (при !х;! » 1) -х|К) х(й-1) (4.3$) шах 1~1 4»» При выполнении условия (4.30) или (4.31) итераци. онный процесс Гаусса — Зейделя называется сходящимся. В этом случае максимальные разности б между зна чениями переменных в двух последовательных итерациях 5 3.
ИТЕРАЦИОННЫЕ МЕТОДЫ Рис. 20. Блок-схема метода 1'аусса — Зейделя 140 гл. 4. системы линеЙных уРАВнении убывают, а сами эти значения стремятся к решению системы уравнений. Для сходимости итерационного процесса достаточно, чтобы модули диагональных коэффициентов для каждого уравнения системы были не меньше сумм модулей всех остальных коэффициентов: ~ап~:= 11а1,1, ю = 1, 2... ~, (4 32) 1Ф1 При этом хотя бы для одного уравнения неравенство. должно выполняться строго. Эти условия являются достаточными для сходимости метода, но они не являются необходимыми, т.
е. для некоторых систем итерации сходятся и при нарушении условий (4.32). Блок-схема алгоритма решения системы п линейных уравнений методом Гаусса — Зейделя представлена на рис. 20. В качестве исходных данных вводятся коэффициенты и правые части уравнений системы, погрешность е, допустимое число итераций НХ, а также начальные приближения переменных т; ~~ = 1, 2, ..., и). Отметим, что начальные приближения можно не вводить в ЭВМ, а полагать их равными некоторым значеничм (например, нулю). Для удобства чтения блок-схемы объясним некоторые обозначения: Й вЂ” порядковый номер итерации; 1 — номер уравнения, а также переменного, которое вычисляется в данном цикле; у — номер члена вида ацх; в правои ,(й) части соотношения (4.29).
Итерации прекращаются либо после выполнения условия (4.30), либо при А = НХ. В последнем случае итерации не сходятся, и после НХ итераций счет прекращается без выдачи результатов. Можно предусмотреть в этом случае также и вывод на печать некоторой поясняющей информации. ~ 4. Задачи на собственные значения 1, Основные понятия. Большое число научно-технических задач, а также некоторые исследования в области вычислительной математики требуют нахождения собственных значений и собственных векторов матриц. Въедем некоторые определения, необходимые для изложения материала данного параграфа.
2 4. ЗАДАЧИ НА СОБСТВЕННЫЕ ЗНАЧЕНИЯ Рассмотрим квадратную матрицу п-го порядка а.а...а1 11 12 21 22 ''' 22~ (4.33) 'л1 'п2 ''' ап Характеристической л1атрицей С данной матрицы А называется матрица вида а — 'Х 11 а 22 а, 21 (4.34) аа1 'а2 называемым характеристическим многочленом. Корни этого многочлена являются собственными значениями матрицы Л. Вектор Х = (х„х1, ..., х„), соответствующий некоторому собственному значению А и удовлетворяющий системе уравнений (4.36) АХ=АХ, называется собственньт вектором матрицы А. Поскольку при умножении собственного вектора на скаляр он остается собственным вектором той же матрицы, то его можно нормировать, В частности, каждую координату собственного вектора можно разделить па максимальную из них или па длину вектора; в последнем случае получится единичный собственный вектор.
Если перейти к координатной форме записи вектора Х, то с учетом (4.33) систему (4.36) можно записать в виде а„х1+ а11х1+ ° ° + а1,х = Х.х„ а.:,х, + а;,х, +... + а„,х„= )х„ ° ° 1 ° ° ' Ф а„,х, + а„,х, +... + а„„х„= Ах„, Здесь А — собственное значение, Š— единичная матрица. Определитель матрицы С является многочленом и-й степени относительно А: ое1 С = соА,"+ с,л" ' +... + с.,А+ с„, (4.35)' Гл. 4. с11стеыы линейных уРАВнен11Й 142 Иногда эту систему уравнений удобно представить в дру- гом виде: (а„— Х) хг+ а,гх, +... + а,„х„= О, а„х, + (агг — Х) х, +... + а,„х„= О, а„,х, + а„,х, +...
+ (а„„вЂ” Х) х. = О. Это уже однородная система п линейных уравнений с и неизвестными. Она имеет ненулевые решения лишь тогда, когда ее определитель равен нулю: де~(А — Ж)=0, причем решение не единственно, поскольку обычно одно уравнение является следствием остальных. На практике обычно при нахождении собственных векторов матрицы одну из его компонент полагают равной некоторому числу, например х, = 1. Остальные компоненты находятся однозначно из подсистемы линейно независимых уравнений, в которой отброшено уравнение, являющееся следствием остальных.
Эта процедура пе влияет на результат решения задачи, поскольку, как уже отмечалось, собственные векторы находятся с точностью до постоянного множителя. П р и и е р. Вычислить собственные числа и собственные векторы матрицы А=( Р е ш е н п е, Составим характеристический многочлен )~ — ~ ' / ~з хН4 ц) г гз п+1о Найдем корни этого многочлена второй степени.' Х' — 7Х + 10 = О, Хг = 2, Лг = 5. Для нахождения собственных векторов Х„Хг, соответствующих собственным значениям Х~, Хг, составим системы уравнений типа (4.36) для каждого пз них, При Х, = 2 получим или в виде системы уравнений: Зх,+ х,=2х„ 2хг + 4хг = 2хг. 5 $. ЗАдАчи нА совственпыи знАчений Записывая полученную систему в виде х,+х,=О, х,+х,=О, замечаем, что уравнения линейно зависимы (даже совпадают). Поэтому оставляем лишь одно из них. Полагаем х, = 1. Тогда х, = — х, = — 1, и собственный вектор, соответствующий собственному значению Х, = 2, имеет вид Х, = (1, — 1) или Х, = е, — е„где с~, е~ — едипичные орты выбранной базисной системы.
Аналогично находим второй собственный вектор, соответствующий собственному значению 1~=5. Опуская комментарии, получаем '*1 1 "1 Зх~ + х~ = 5х„— 2х, + х~ = О, 2х1 + 4хг = 5хг, '2х~ — х2 = О, Отсюда х,=1, х,=2, Х,=е,+2е~. Вектор Х, нормирован; нормируем также вектор Х2, разделив его компоненты на наибольшую из них. Получим Х, = 0.5е, + е,, Можно также привести векторы к единичной длине, разделив их компоненты на значения модулей векторов. В этом случае Х1 = =(в, — е.,), Х,, = =(в1+ 2в,,), Мы рассмотрели простейший пример вычисления собственных значений и собственных векторов для матрицы второго порядка.
Нетрудно также провести подобное решение задачи для матрицы третьего порядка и для некоторых весьма специальных случаев. В общем случае, особенно для матриц высокого порядка, задача о нахождении их собственных значений и собственных векторов, называемая полной проблемой собственных значений, значительно более сложная. На первый взгляд может показаться, что вопрос сво'дится к вычислению корней многочлена (4.35). Однако здесь задача осложнена тем, что среди собственных значений часто встречаются кратные. И кроме того, для произвольной матрицы непросто вычислить сами коэффициенты характеристического многочлена, 14$ гл.
4. системы линейных уРАВнениЙ В=Р 'АР, (4.37) то их собственные значения совпадают (здесь Р— неко торая матрица) . Преобразование подобия (4.37) можно использовать для упрощения исходной матрицы, а задачу о вычислении ее собственных значений свести к аналогичной задаче для более простой матрицы. Очевидно, самым лучшим упрощением матрицы (4.33)' было бы приведение ее к треугольному виду Р Р Р а11 а12 ' ' ° а1п / аале ° ° ° азу ° ° О аи Тогда матрица (4.34 )также имела бы треугольный вид. Как известно, определитель треугольной матрицы равен произведению ее диагональных элементов, поэтому характеристический многочлен (4.35) в этом случае имеет вид 41е$ С = (а,1 — Ц (а„— Х), .. (а„,„— Ц. (4,38) Собственные значения матрицы, равные корням этого многочлена, можно сразу получить: Р Р Р ~11 = а111 ~я = а22~ ° - 1~п аул (4.39) Таким образом, собственные значения треугольной матрицы равны ее диагональным элементам.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
