Б.П. Демидович, И.А. Марон - Основы вычислительной математики (1132358), страница 37
Текст из файла (страница 37)
Расставленные там единицы помога1от находить для хг соответствующие коэффициенты в отмеченных строках. 275 б З) метод гдьссл Таблнпа 13 Схема единственного деления Сеьбьдные едена Рендела ехе вы «4 к, Для контроля вычислений используются так называемые «контрольные суммы» а,.е — —,~.", а(у (1=1, 2, ..., 5), (5) 1 1/ помещенные в столбце чп и представляющие собой сумму элементов строк матрицы исходной системы (1), включая свободные члены. ап ан) а«1 а41 1 аы а,е а)м ае, Ь, (ы аее а(1) аее а(') 1 ахе аее аее аен Ь)е (1) а,е (1) аее а'" аее Ь(1) ее аы аы ае, ам Ь а(1' (Н аее а(') 44 Ь(1! аы аее ам аее Ь И) аее (1) аее а(1) аее Ь(1) а)е а„ аее аее ь а'1' аее (П аее , (1) аее Ь(1' 14 276 Решение систем линейных хгхвнений (гл. Рш ~ а; х = а (1 = 1, 2, 3, 4) (4) /=1 будет иметь неизвестные х, связанные с прежними неизвестными х7 соотношенинми хг — — хг+1 (/= — 1, 2, 3, 4). (5) В самом деле, подставляя формулы (5) в уравнение (4), в силу системы (1) и формул (3) получим тождество ~ а;ру+ ~ а;7 — — ~~", а,.
=аы (7'=1, 2, 3, 4). 1=1 1=1 ' /=1 Вообще, если над контрольными суммами в каждой строке проделывать те же операции, что и над остальными элементами этой строки, то при отсутствии ошибок в вычислениях элементы столбца ~ равны суммам элементов соответствующих преобразованных строк. Это обстоятельство служит контролем прямого хода. Обратный ход контролируется нахождением чисел ху, которые должны совпадать с числами ху+1.
П р и м е р. Решить систему 7,9х, + 5,6х + 5,7х, — 7,2х, = 6,68; 8,5хг — 4,8хя+ 0,8хз+ 3,5ха = 9,95; 4,3х, + 4,2х, — 3,2х, + 9,3ха = 8,6; 3,2х, — 1,4х — 8,9х,+З,Зх, = 1. (6) Решен и е. В раздел А таблицы 14 впишем матрицу коэффициентов системы, ее свободные члены и контрольные суммы. Далее, заполняем последнюю (пятую) строку раздела А, деля первую строку на 7,9 (на а,д). Переходим к заполнению раздела Аг таблицы. Взяв любой элемент раздела А (не находящийся в первой строке), вычитаем из него произведение первого элемента его строки на последний элемент столбца, к которому он принадлежит, и записываем на соответствующее место в разделе А, схемы. Например, выбрав паз = — 8,9, будем иметь: а",,' = а„ вЂ” а„э,а = — 8,9 — 3,2 0,72152 = — 11,20886.
Чтобы получить последнюю строку раздела А„ делим все члены первой строки этого раздела на а~,',> = — 10,82531. Например, л(» Если аы принять за новые свободные члены в системе (1), то преобразованная линейная система 277 МЕТОД ГАУССА Таблица 14 Решение сястемы по схеме единственного деления Сеабадаые рээдеды Реедеды 41ЕЫЫ эе 0,72152 — 0,91139 0,84557 2,36456 0,708 86 †!0,82531 1,15190 — 3,66835 11,24682 2,76265 !3,21898 4,96405 6,2!645 — 1,70582 — 5, 33292 — 6,30254 — 11,20886 0,49263 — 1,03894 — 0,25520 0,19849 5,2580! — 2,64198 12,80374 — 9,63845 — 6,87000 — 9,40172 14,41573 2,40525 — 1,86372 — 2,09836 — 0,76536 — 9,83768 — ! 7,32294 0,567 90 Аналогичным путем заполняются остальные разделы таблицы.
Например, (Э) (1) (1) е(1) аее = а„— а„й„= = 6,21645 — ( — 3,66835) ( — 1,03894) = 2,40525. Для нахождения неизвестных используем строки, содержащие единицы, начиная с последней (отмеченнеш строки). Неизвестное хд пРедставлает собой свободный член последней стРоки Раздела Аа: х, = 541) = 0,56790. Значения остальных неизвестных х, х„х получаются последовательно в результате вычитания из свободных членов отмеченных 7,9 8,5 4,3 3,2 5,6 — 4,8 4,2 — 1,4 5,7 0,8 — 3,2 — 8,9 — 7,2 3,5 9,3 3,3 6,68 9,95 8,6 1 0,567 90 0,426 30 О,!24 80 0,96710 18,68 17,95 23,2 — 2,8 — 2,14876 13,03239 — 10,36658 — 27,16062 1,56790 1,56790 1,42630 1,12480 1,96710 278 Решение систем линейных уРЛВнений (гл.
чш строк суммы произведений соответствующих коэффициентов Ьп на < > ранее найденные значения неизвестных. Имеем: «а = Ьзв — Ье1ла = 0 76536 — ( — 2 09836) 0 56790 = 0 42630' ж,=܄— ЬЕ4х,— Ь„х = ы> и> и) = — 0,25520 — ( — 1,03894) 0,56790 — 0,49263 0,42630= 0,12480; х, = Ьш — Ьыха — Ь,х, — Ьы в = 0,84557 — ( — 0,91139) Х Х0,56790 †,72!52 0,42630 — 0,70886 0,12480 = 0,96710.
Итак, х = 0,96710; х, = 0,12480; х = 0,42630; х, = 0,56790, Текущий контроль вычислений осуществляется с помощью столбца ~, над которым производятся те же действия, что и над остальными столбцами. В результате: 1) сумма элементов каждой строки схемы (не принадлежащих столбцу ~) должна быть равна элементу этой строки из столбца ~; 2) корни хп соответствующие столбцу ~~~~~, должны быть на единицу больше соответствующих корней системы.
Кстати, если учесть единицы, написанные в разделе В, то опять получится, что и в этом разделе элементы столбца '«~ являются суммами элементов отвечающих им строк. В нашем случае первое и второе условия выполняются с точностью до единицы последнего разряда. Следовательно, почти достоверно, что вычисления выполнены правильно. Заметим, что если матрица системы †симметрическ, то соответствующие части разделов А, Аы А„ ... схемы единственного деления также получаются симметрическими. Это обстоятельство можно использовать для упрощения таблицы.
Нетрудно оценить число Ь( арифметических действий, необходимых для решения линейной системы с и неизвестными методом Гаусса [5) (не учитывая контроля). Для прямого хода требуется следующее число умножений и делений: л(л+1)+(л — 1) л+... +1 2=(1'+2'+... +л')+ + ) л (И+1) (л+2) л (а — !) и столько же вычитаний. Для обратного хода потребуется 2 умножений н делений н такое же количество вычитаний. Следова- 270 уточнение кОРней з 41 тельно, общее количество арифметических действий в методе Гаусса есть 2л (л+1) (я+2)+ 3 при л) 7.
Таким образом, время, необходимое для решения линейной системы методом Гаусса, примерно пропорционально кубу числа неизвестных. Например, для решения методом Гаусса системы 100 линейных уравнений со 100 неизвестными на быстродействующей машине, выполняющей 1Ое операций в секунду, потребуется время Т= 10' 1О е = 100 сек. Фактическое машинное время будет значительно больше ввиду наличия в программе, кроме аряфметических действий, друтих операций (переадресация, логические операции, пересылки, формирование и др.). й 4. Уточнение корней Полученные методом Гаусса приближенные значения корней можно уточнить. Покажем, как вто делается, если поправки корней малы по абсолютной величине. Пусть для системы Ах =Ь найдено приближенное решение х .
Полагая «=х,+Ь, б, для поправки Ь = ° корня хе будем иметь уравнение б„ А (хе+ Ь) = Ь или Аб=е, где в= Ь вЂ” Ах — невязка дяя приближенного решения х . Таким образом, чтобы найти Ь, нужно решить линейную систему с прежней е, . Для этого доста- мзтрицей А и новым свободным членом е= ела точно к основной схеме вычислений присоединить столбец в свобод- Ь ных членов и преобразовать его по общим правилам.
Поправки Ь ы ю ., Ь„, как обычно, определяются из отмеченных строк, причем коэффициенты при этих неизвестных поправках уже имеются готовыми 280 РЕШЕНИЕ СИСТЕМ ЛИНЕЙНЫХ УРАВНЕНИЙ [Гл. чш в таблице. Заметим, что преобразованные коэффициенты матрицы А можно не уточнить, так как при малых невязках соответствующие ошибки будут обладать более высоким порядком малости. При мер. Решить методом Гаусса с тремя знаками (например, на счетной линейке или вручную) систему бх, — х — х = 11,ЗЗ; — х1+6хз хз=32' — хт — хз+бхз=42 Используя полученные значения как начальные приближения, уточнить корни до 10 з. Р е ш е н и е. Применяем обычную схему единственного деления (таблица 16), выполняя все действия с тремя значащими цифрами.
Таблица !б Рточненне корней, вычисленных методом Гаусса Имеем приближенные значения корней: 281 9 51 МЕТОД ГЛАВНЫХ ЭЛЕМЕНТОВ Полставляя эти числа в данную систему (1), вычисляем соответствующие невязки (т. е. разности мехгду правой и левой частями системы(1)) Используя зги значения в качестве свободных членов (таблица 15), получаем поправки корней 51ю — — — 0,0039; 5 "' = — 0,0011; 6140 = — 0,0025. Отсюда находим уточненные значения корней хг=4,6661; х =-7,6189; х =9,0475, причем невязки равны Ь= — 210 4, 5 =210-4 5 0 Иногда требуется определить возможную ошибку Лх корня х линейной системы по известным малым ошибкам ЛА и ЛЬ матрицы А системы и ее свободного члена Ь. Имеем: (2) Ах=Ь (3) (А+ ЛА) (х+ Лх) =- Ь+ ЛЬ. Отсюда, пренебрегая .малым членом ЛА Лх, получим: Ах+ АЛх+ ЛАх = Ь+ ЛЬ или АЛх = ЛЬ вЂ” ЛАх.
(4) Таким образом, для приближенного нахождения Лх можно использовать схему Гаусса для основной системы (2), пополнив зту схему новым столбцом свободных членов ЛЬ вЂ” ЛАх. $ 5. Метод главных злементов Пусть дана линейная система а„х,+а х,+... +а,„х„=а, „ азгх, + а„х, +... + а,„х„= а, „+м агах,+а„х,-(-... +а„„х„=а„„+,. 282 Решение систем линеЙных уРхзнений (гл.
Ун! Рассмотрим расширенную прямоугольную матрицу, состоящу!о из коэффициентов системы и ее свободных членов, аы а!л ... а!! .. ° а!а "° а!» а!, «+! ал! а»» " ал! ". аьт" алл а», л+! ап ал ... ау... а! ... аул сч ар, а ... арг ... )ар ) ... арл ар л+! ал! алл ° ° ° ал! ° ° ° алт ° ° ° алл ал л+! Выберем ненулевой, как правило, наибольший по модулю, не принадлежащий к столбцу свободных членов (афп+ 1) элемент аре матрицы М, который называется главным элементом, и вычислйм множители ага лт! —— —— аре для всех !ар. Строка с номером р матрицы М, содержащая главный элемент, называется главной строкой. Далее, произведем следующую операцию: к каждой неглавной строке прибавим главную строку, умноженную на соответствующий множитель !и! длв этой строки.
В результате мы получим новую матрицу, у которой д-й столбец состоит из нулей. Отбрасывая этот столбец и главную р-ю строку, получим новую матрицу М!'! с меньшим на единицу числом строк и столбцов. Над матрицей М!т! повторяем те же операции, после чего получаем матрицу М!'>, и т. д. Таким образом, мы построим последовательность матриц Мы! М!л-м последняя из которых представляет двучлеиную матрицу-строку; ее также считаем главной строкой. Для определения неизвестных м! объединяем в систему все главные строки, начиная с последней, входящей в матрицу М<л-'!.
После надлежащего изменения нумерации неизвестных получается система с треугольной матрицей, из которой легко шаг за шагом найти неизвестные данной системы (1). Метод главных элементов всегда применим, если определитель системы ) аы ° ° алл бе1 А = ~ ..... ф О. ал, ... алл й 6) пгимвнхнив мвтодь гатссь для вычисления опгвдвлитвлвй 283 Заметим, что метод Гаусса является частным случаем метода главных элементов, а схема метода Гаусса получается, если за главный элемент всегда выбирать левый верхний элемент соответствующей матрицы.
ф 6. Применение метода Гаусса для вычисления определителей Пусть аы аы ° ° ° а»в ам а„... а,л ал» ал» ° ° алв о =бе! А. (2) Рассмотрим линейную систему Ах = О. (3) При решении системы (3) по методу Гаусса мы заменяли матрицу А треугольной матрицей В, состоящей из элементов отмеченных строк, Ь Ь, ...
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
