1626435584-7c6402f545ecf856225d6cf8d21519c9 (844233), страница 29
Текст из файла (страница 29)
Пусть матрица А содержит много нулевых элементов, расположенных в матрице не беспорядочно, а плотными массивами на заранее известных местах. Тогда расчет по методу Гаусса можно организовать так, чтобы не включать эти элементы. Тем самым объем вычислений и требуемая память уменьшаются, зачастую очень сильно. На рис. 25 приведйны структуры матриц, которые нередко встречаются в задачах физики и техники и допускают такое ускорение расчета; горизонтальными линиями изображены положения ненулевых элементов, окаймлены границы массивов нулевых и ненулевых элементов.
К таким матрицам относятся ленточные (а),. яшичные (в), квазитреугольные (д), почти треугольные (е) и многие другие*). Можно показать, что при обходе нулевых элементов решение системы с почти треугольной матрицей требует ') Напомним принятую терминологию. Матрица называется верхней треугольной, если все элементы ниже главной диагонали равны нулю (ам=о при Г ) й); аналогично определяется нижняя треугольная матрица.
Почти треугольной называется матрица, элементы которой удовлетворяют соотношению азь = = О при г)а+К т. е, ненулевые элементы имеются не только в верхнем треугольнике, но н в примыкающей к нему «боковой диагонали», Трехдиагональной называется матрица, у которой ненулевые элементы имеются только на главной диагонали и прнмынающнх к ней, т. е. ага=о прн,'1 — й ~ ) и Нетрудно записать определенна других типов матриц, иаображенных на рис. 25. 133 линейные системы всего 2а' действий, а с ленточной-даже '/,й'и, где А — ширина ленты, т.
е. выигрыш во времени счета очень велик. Выбор наиболыпего элемента в таких расчетах делать нельзя, ибо перестановка столбцов разрушает специальную структуру матрицы. В матрицах с симметричной структурой недопустим е1 Ряс. 25, даже выбор главного элемента. Но обычно в этом нет необходимости, поскольку подобные физические задачи приводят, как правило, к хорошо обусловленным матрицам с большими элементами на главной диагонали, для которых ошибки округления в методе Гаусса невелики. Наиболее важным частным случаем метода Гаусса является метод прогонки, применяемый к системам с трехдиагоналвной матрицей 1они часто встречаются при решениях краевых задач для дифференциальных уравнений второго порядка). Такие системы обычно записывают в каноническом виде а;хг ь — Ь!х,+ с;х;„= 4, 1 ~ 1 ~ и, а,=с„=б.
СИСТЕМЫ УРАВНЕНИИ ггл. у Формула (1О) называется разностным уравнением второго порядка, или трехточечным уравнением. В этом случае прямой ход (без выбора главного элемента) сводится к исключению элементов аь Получается треугольная система, содержащая в каждом уравнении только два неизвестных, х, и х„.„.
Поэтому формулы обратного хода имеют следующий вид: хг=$г„х!»г+т)!»г, г=п, и — 1...,, 1. (11) Уменыпим в формуле (11) индекс на единицу и подставим в уравнение (10): а! ($гхг+ тг!) — Ь,хг+ с,х„, = с(!. Выражая отсюда х! через хг,„получим с! агч! — е! х! = х!»г+ ь! — аг1! ь,— Д,' Чтобы это выраженне совпало с (11), надо, чтобы стоящие в его правой части дроби были равны соответственно «!»г и Отсюда получим удобную запись формул прямого хода 5!+ ! — — с;/(Ь, — аД;), 12) т1г„= (арй — г(!)/(Ь! — аД,), г = 1, 2, ..., и. Попутно можно найти определитель трехдиагональной матрицы л бе(А =П (аД! — Ьс) (13) г=! Вычисления по формулам прогонки (12) — (11) требуют всего 3п ячеек памяти и 9п арифметических действий, т. е.
онн гораздо экономнее общих формул метода исключения. В формулах прямого и обратного хода начало счета «замаски- ровано»: для качала (развязки) расчета формально требуется задать величины «„ ттд и х„„, которые неизвестны. Однако перед этими величинами в формулах стоят множители а„ или 5„»г с„, равные нулю.
Это позволяет начать вычисления, полагая, напри- мер, $г =т)! =х„, =О. Покажем, что если выполнено условие преобладания диа ональ- ных элементов ! Ь, ! - ( а, ! + ! с! ) (14) (причем хотя бы для одного ! имеет место неравенство), то в фор- мулах прямого хода (12) не возникает деления на нуль, и тем самым исходная система (10) имеет единственное решение. Для этого предположим, что )~!) ( 1 при некотором значении индекса. 'Тогда легко проверяется цепочка неравенств ! $! «г ) =! с, ~/( Ь! — аД! ! =" ! с; )/() Ь! ) — ) а! ! )1$ ! !) ~ ( ~ с! )/(! с; ) + ) а! ! — ) а! ( х ) В! () ( 1. ЛИНЕЙНЫЕ СИСТЕМЫ Поскольку можно положить $т=О, отсюда по индукции следует ~с,~ ~1; значит, )Ь,— аД;~ ~с,(~0, что и требовалосьдоказать.
При выполнении условия (14) формулы прогонки не только безавостны, но и устойчивы относительно ошибок округления и позволяют успешно решать системы уравнений с несколькими сотнями неизвестных. Условие (14) является достаточным, но не необходимым условием устойчивости прогонки. Конечно, можно построить примеры неустойчивости при несоблюдении этого условия. Но в практических расчетах для хорошо обусловленных ' систем типа (10) прогонка часто оказывается достаточно устойчивой даже при нарушении условия преобладания диагональных элементов.
Заметим, что к линейным системам с трехдиагональной матрицей обычно приводят трехточечные разностные схемы для дифференциальных уравнений второго порядка (глава Ъ'П1, й 2). 6. Метод квадратного корня. Этот метод пригоден только для линейных систем с эрмитовой ") матрицей А =Атт, и формулы расчета при этом несколько сложней, чем в методе Гаусса. Зато метод квадратного корня вдвое быстрей метода Гаусса. Метод основан на представлении эрмитовой матрицы системы в виде произведения трех матриц 5нР5 (15) о пно (а, О ам = „л, атас(нзн = ~х~ ~Й,ззгазн; ограничение верхнего предела в сумме связано с обращением в нуль элементов 5 ниже главной диагонали.
Последнее равенство можно записать в такой форме: а ааа=-~ Нн ~з;а~а а аа, = ~х, 'с(нз,'аан, з=! й<1, ) Напомним, что матрица называется эрмитовой, если а~а=или эрмнтова а. матрица с вещественными элементами является симметричной, Здесь Р— диагональная матрица с элементами йн= + 1, 5— верхняя треугольная матрица (ам =0 при т') й), а 5н — эрмитово сопряженная к ней нижняя треугольная матрица. Для полной определенности разложения потребуем вещественности и положительности диагональных элементов зн) О. Перепишем соотношение (!5) ц следующем виде: 136 СИСТЕМЫ УРАВНЕНИЯ [гл.
ч или окончательно А †! г(АА=э(дп аАА — ~ !(!!~ а!А Г, !=1 А — ! зАА=~( а„—,Р, !(!!!з!А!', !=1 (16) А — ! ам = (ам — ~ !1!!зэьз!!)/(ВАА!(„А) при й+1 ~1еь и. !)е1А =Ц !(!!з)!. !=1 Метод квадратного корня требует примерно !/,и' арифметических действий, т. е. при больших п он вдвое быстрей метода Гаусса, и занимает вдвое меньше ячеек памяти, Это понятно, ибо метод использует информацию о симметрии"матрицы.
Кроме того, для ленточной, ящичной и некоторых других структур матрицы А (рис. 25, а — г) матрица 5 будет иметь аналогичную структуру, т. е. содержать массивы нулевых элементов на заранее известных местах. Учет этого позволяет сильно сократить объем вычислений; как и в методе Гаусса. Однако заметим, что для ленточных матриц с узкой лентой, особенно для трехдиагональных, метод квадратного корня по скорости мало отличается от метода Гаусса и может быть даже медлен- В этих формулах сначала полагаем й= 1 и последовательно вычисляем все элементы первой строки матрицы 5; при /!= 1 все суммы в формулах (18) отсутствуют. Затем полагаем а 2 и вычисляем вторую строку 'и т, д. Когда все элементы матриц найдены, то решение линейной системы Ах=Э сводится к последовательному решению трех систем, двух треугольных и одной диагональной: 3"г=д, Оу=г, Зх=у, (17) что делается обычным обратным ходом по формулам 9, = Ьт/з!,б!!, с — ! 9! = (Ь! — ~ дп9!3!1)/з!!г(!!, !=2, 3, ..., и; (18) хп = 9а/зпп~ Л х; =(9; — ~ зпх,)/зи, !=п — 1, и — 2, ..., 1.
! !+! Определитель матрицы вычисляется по формуле ЛИНЕИНЫЕ СИСТЕМЫ !Зт ней, ибо среди производящихся в нем действий есть извлечение корня, медленно выполняемое на ЭВМ. Наиболее частый на практике случай эрмитовой матрицы— это вещественная симметричная матрица А. Тогда никаких комплексных чисел прн вычислениях не возникает, так что матрица 5 тоже вещественная. Если вдобавок матрица А положительно определенная (для этого необходима и достаточна положительность всех ее главных миноров), то все оп=1, и формулы (16) — (19) можно немного упростить.
Расчет по формулам (16) невозможен, если при некотором значении индекса элемент з„1 = 0 (в частности, зы = 0 при ам = О). От этого можно избавиться, переставляя на место ае„другой диагональный элемент аль О, т. е. надо переставить и строки и столбцы, на пересечении которых лежат эти два элемента. Метод квадратного корня применяют в основном при численном решении интегральных уравнений Фредгольма с симметричным ядром, ибо эта задача сводится к линейной системе с симметричной матрицей, обычно не содержащей нулевых элементов (при регуляризации таких задач симметрия матрицы сохраняется).
7. Плохо обусловленные системы. Если система Ах=Ь плохо обусловлена, то это значит, что погрешности коэффициентов матрицы и правых частей нли погрешности округления при расчетах могут сильно исказить решение. Для уменьшения погрешностей округления можно было бы провести на ЭВМ расчет с двойным или тройным числом знаков. Но при наличии погрешности коэффициентов это бесполезно, и нужно регуляризовать исходную задачу.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
