Амосов А.А., Дубинский В.А., Копченова Н.В. Вычислительные методы для инженеров (1994) (1095853), страница 28
Текст из файла (страница 28)
Для того чтобы убедиться в ошибочности этого мнения, умножим каждое из уравнений системы (5.1) на постоянную а ~ О. Ясно, что такое преобразование никак не меняет решение системы и его чувствительность к малым относительным ошибкам в данных. Однако определитель умножается на число а~, и поэтому с помощью выбора а может быть сделан как угодно большим или малым. Подчеркнем, что число обусловленности сопд(А) при таком преобразовании системы не меняется в силу свойства За. 3 а м е ч а н и е 3. Вычисление чисел обусловленности и = ~А '~ ° ~Ь~/~~х)~ и сопс1(А) = ))А '(~ ° 1А~( непосредственно по указанным формулам предполагает предварительное вычисление обратной матрицы А '. Вследствие большой трудоемкости этой операции (как показано в ~ 5.6, для ее выполнения в общем случае требуется примерно 2тэ арифметических операций) на практике избегают такого способа вычисления.
При этом важно отметить, что в большинстве случаев достаточно лишь грубой оценки числа обусловлен- 136 аде 6*(х ) = $х — х*~/$х'~, 6(А ) = ~А — А ~/~А~. и В данном случае невязка г имеет вид г = Ь вЂ” Ах* =.А,х* — Ах"= = (А, — А) х". Применяя неравенство (5.19), получим цепочку , неравенств ности с точностью до порядка. С эффективными методами, дающи- ми оценки величин г~ и сопй(А), можно познакомиться в [67], ~86]. Проверить чувствительность решения системы Ах = Ь к погрешностям можно и экспериментально.
Для этого достаточно решить задачу несколько раз с несколькими близкими к Ь правыми частями Ь'", Ь, ..., Ь . Можно ожидать, что величина и = шах —.—;0 — даст (2) (и) 14 ХЬ оценку значения иб. Во всяком случае эта величина дает оценку снизу, так как иб < иб ~ сопй(А). з 5.5 Метод Гаусса Рассмотрим один из самых распространенных методов решения систем линейных алгебраических уравнений — метод Гаусса', Этот метод (который называют также летодои последовательно1о иенлн)пения неизвестных) известен в различных вариантах уже более 2000 лет. Вычисления с помощью метода Гаусса состоят из двух основных этапов, называемых пряиыл) ходом и обратныл ходо.и (обратной подстановкой). Прямой ход метода Гаусса заключается в последовательном исключении неизвестных из системы (5.1) для преобразования ее к эквивалентной системе с верхней треугольной матрицей.
Вычисления значений неизвестных производят на этапе обратного хода. 1. Схема единственного деления. Рассмотрим сначала простейший вариант метода Гаусса, называемый схе иой единственного деления. П р я м о й х о д состоит из т — 1 шагов исключения, 1-й ш а г. Целью этого шага является исключение неизвестного х) из уравнений с номерами 1 = 2, 3, ..., т. Предположим, что коэффициент а)) Ф О. Будем называть его ~лавныл) (или ведущим) элементом 1-~о шага.
Найдем величины (5.29) )ып — — ад/а)) (1 = 2, 3, ..., т), называемые иноясителялюи 1-1о шага. Вычтем последовательно из второго, третьего, ..., т-го уравнений системы (5.1) первое уравнение, умноженное соответственно на а2), аэ), ..., а„). Это позволит обратить в 1 17 ) Карл Фридрих Гаусс (1777 — 1855) — немецкий математик и физик, рабо— ты которого оказали большое влияние на дальнейшее развитие высшей алгебры, геометрии, теории чисел, теории электричества и магнетизма.
нуль коэффициенты при х) во всех уравнениях, кроме первого. В ре- зультате получим эквивалентную систему а))х~ + а)гхг + а[зхз + ... + а)„хн = Ь) агг'~+ а,'з'хз+ -+ а,'."х~= Ь[" а'1' хг+ а'1' хз+ .. + а''> х„= Ь[1) зг зз з " . зн н з [',5.30) в которой а[.'> и Ь[1> (1, у' = 2, 3, ..., т) вычисляются по формулам [,5.31) аф = а[2- Кач, Ь'," = Ь -И[)Ь) 2-й ш а г. Целью этого шага является исключение неизвестного хг из уравнений с номерами 1 = 3, 4, ..., т.
Пусть агг~ Ф О, где агг~ коэффициент, называемый главны и (или ведущим) элементом 2-[о ша)а. Вычислим множители 2-го шага И[г агг /агг [ 1) / [ 1) (1' = 3, 4, ..., т) а11Х1+ а12Хг + а)ЗХЗ +" + а1тХн = Ь1 22 х2+ агз хз+ .. + аг)з хи= Ь2 а[г) хз + ... + а[2) х — Ь[2) зз '" зн н з > [',5.32) а[2) хЗ + .. + а[2) хн — Ь[2) Здесь коэффициенты а[г' и Ь[2' (1, у' = 3, 4, ..., т) вычисляются по формулам а'2' = а[" — )[га''.> [г' 1> 12 2> ь[.2) = ь[.1) — Р; Ь[ 1) .
1 1 Аналогично проводятся остальные шаги. Опишем очередной Ь-й шаг. Ь-й ш а г. В предположении, что [лавнз[й [ведущий) э*ел)ент й-го шага аф)> отличен от нуля, вычислим множители Й-зо шаза ,и,). = аф))/ай)) [',1= Й+ 1, ..., т) )зя и вычтем последовательно из третьего, четвертого, ..., т-го уравнений системы 15,30) второе уравнение, умноженное соответственно на дзг, 042 ",))нг В результате получим систему а>>х~ + а>гхг + а>ззз + ... + а>взт = Ь> а11>хг+ а11>хз+.... + а>1> з = 6' "' гг гз "' гв т г а1г' хз + ... + а> г > с = 61 г > зз " зв в з (5.33) а1т 1> з = 6<в 1'.
тт т т Матрнца А1т 1> КОтсрОй яВЛяЕтея ВЕрХНЕй трЕуГОЛЬНОй. На ЗтОМ ВЫЧИС- ления прямого хода заканчиваются. О б р а т н ы й х о д. Из последнего уравнения системы (5.33) находим х . Подставляя найденное значение хт в предпоследнее уравнЕние, получим х 1. Осуществляя обратную подстановку, далее послеДовательно нахоДим хт г, хт з, ..., ю>. ВычислениЯ неизвестных зДесь проводятся по формулам з = 61т>>/а>" '> т т вт > (5.34) зй = (Ьйй>> — аЬйй',> хй+1 — ... — аЬй 1>хт)/аД1', (Й= т — 1, ...,1). Т р у д о е м к о с т ь м е т о д а. Оценим число арифметических операций, необходимых для реализации схемы единственного деления. Вычисления 1-го шага исключения по формулам (5.29), (5.31) требуют выполнения ш — 1 деления, (ти — 1)»з умножений и (»з — 1)»> вычитаний, т.
е. общее число арифметических операций составляет Я1 = 2(т — 1)г + 3(т — 1). Аналогично, на 2-м шаге требуется ~г —— = 2(т — 2)г + 3(т — 2) операций, а на Ь-м шаге — ' Яй = 2(пз — Ь)г + + 3(т — й) операций. Подсчитаем теперь приближенно общее число Я арифметических операций прямого хода, считая размерность системы т достаточно большой; т-1 в-1 т-1 т-1 т-1 д ~ д — 2Я (~ Ь)г~.3Е (»> й)=2Х Ьг-~-3Е й= й=1 й=1 й=1 й=1 й=1 2(т — 1) т (2»> — 1) 3(»> — 1)»> 2 з 6 2 3 139 и вычтем последовательно из (Й + 1)-го, ..., т-го уравнений полученной на предыдущем шаге системы М~ уравнение, умноженное соответс- ТВЕННО На >>й 1 й, >>й+г,й, ".
Ртй. После (т — 1)-го шага исключения получим систему уравнений Пример 5.7. Методом Гаусса решим систему 10х1 + 6хз + 2хз = 25 5х1 + . хз — 2хз + 4ха = 14, Зх1 + 5хз + хз — хз = 10, 6хз — 2хз + 2а~ — — 8. (5.35) П р я м о й х о д. 1-й ш а г. Вычислим множители аз~ = ад/ап = 5/10 = 0.5, аз~ — аз~/ап = 3/10 = 0.3, д4~ = ап/ап = О/10 = О, Вычитая из второго, третьего и четвертого уравнений системы (5.35) первое уравнение, умноженное на ать уз~ и д.п соответственно получим 10х1 + бхай + 2хз = 25, — 2хз — Зхз + 4хз = 1.5, 3.2хз + 0.4хз — хз — — 2.5, 6хг — 2хз + 2ж~ = 8.
(5.36) 2-й ш а г. Вычислим множители рзз = а<зш/а<зш = 3.2/( — 2) = — 1.6, н~з— = 6/( — 2) = -3. Вычитая из третьего и четвертого уравнений системы (5.36) второе уравнение, умноженное на дзз и д4з соответственно, приходим к системе 10з1 + 6хз + 2хз = 25, — 2хз — Зхз + 4х~ — — 1.5, — 4.4хз + 5 4х~ = 4 9 — 11хз + 14ж~ = 12.5. (5.37) 3-й ш а г. Вычисляя множитель р~з —— ( — 11)/( — 4.4) = 2.5 и вычитая из четвертого уравнения системы (5.37) третье уравнение, умноженное на р.д, приводим систему к треугольному виду: 10х1 + 6хз + 2хз = 25, — 2хз — Зхз + 4х4 = 1.5, — 4.4хз + 5.4ж~ — — 4.9, 0.5х4 = 0.25.
(5.38) О б р а т н ы й х о д. Из последнего уравнения системы находим х~ = 0.5. Подставляя значение хз в третье уравненйе, находим хз 140 Как нетрудно видеть, для реализации обратного хода по формулам (5.34) нужно всего пР операций, что при больших пг пренебрежимо мало по сравнению с числом операций прямого хода. Таким образом, для реализации метода Гаусса требуется примерно (2/3)тз арифметических операций, причем подавляющее число этих действий совершается на этапе прямого хода. = (4.9 — 5.4х4)/(4.4) = О.5. Продолжая далее обратную подстановку, получаем х~ = (1.5 + Зх~ — 4х4)/(-2) = 1, х1 = (25 — 6з~ — 2х4)/10 = 2.
Итак, х1 = = 2, г~ = 1, хЭ = -0.5, х4 = 0.5. Результаты вычислений можно свести в следующую таблицу. Таблица 52 а! аю аа а$4 Ь~ ФФ х. Исходная система 1-й шаг прямого хода 2-й шаг прямого хода 3-й шаг прямого хода и обратный ход Необходимость выбора главных элемент о в. Заметим, что вычисление множителей, а также обратная подстановка требуют деления на главные элементы аи1'.
Поэтому если один из главных элементов сказывается равным нулю, то схема единственного деления не может быть реализована. Здравый смысл подсказывает, что и в ситуации, когда все главные элементы отличны от нуля, но среди них есть близкие к нулю, возможен неконтролируемый рост погрешности. Пример 5.8. Используя метод Гаусса, решим систему уравнений 2х1 — 9х2 + 5хэ = -4, 1.2х1 — 5.3999хг + 6хэ = 0.6001, х1 — 4~ — 7.5хз = -8.5 (5.39) на 6-разрядной десятичной ЭВМ. 141 10 5 3 0 10 0 0 0 10 0 0 0 10 0 0 О 6 2 1 -2 5 1 6 -2 6 2 -2 -3 3.2 0.4 6 -2 6 2 — 2 -3 0 -4.4 0 — 11 6 2 -2 -3 0 -4.4 0 0 0 4 — 1 2 0 4 -1 2 О 4 5.4 14 0 4 5.4 0,5 25 14 10 8 25 1.5 0.5 2.5 0.3 8 0 1.5 4.9 -1.6 7.5 -3 25 2 1.5 1 4.9 -0 5 0.25 0.5 П р я м о й х о д. 1-й ш а г.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
