Амосов А.А., Дубинский В.А., Копченова Н.В. Вычислительные методы для инженеров (1994) (1095853), страница 29
Текст из файла (страница 29)
Вычисляем множители а㻠— — 0.6 и»аз» = = 0.5 и преобразуем систему к виду 2х» — 9х~ + 5.хз — -4, 0.0001х2 + Зхз — 3.00011 3.5х2 — 10хз = -6.5 ° (5.40) Все вычисления на этом шаге выполняются без округлений. 2-й ш а г. После вычисления множителя дзз —— 3.5/0.0001 = 35 000 последнее уравнение системы должно быть преобразовано к виду аз»з> хз = Ь»з~, где аД> = -10 — 3'кзз = 105010 Ь»х» = -6 5 — 3 0001'рзг = 105010. Однако на используемой ЭВМ будет получено уравнение -105010хз ='-105011. (5.41) Действительно, коэффициент аД' определяется точно, так как при его вычис- лении не возникает чисел, мантиссы которых имеют более 6 разрядов.
В то же время при вычислении Ь»» умножение коэффициента 3.0001 на дзз дает 7- разрядное число 105003.5, после округления которого до 6 разрядов получится 105004. Вычисление Ь» з~ завершается выполнением операции вычитания: з Ьз»з» ~ -6.5 — 105004 = —.105010.5. После округления последнего числа до 6 з = (3.0001 — 3 з)!0.0001 = (3.0001 — З.ООООЗ)УО.0001 = 0.7, х»' = (-4 + 9хз — 5хз)Г2 ( 4 + 6 3 5.00005)/2 = 1 350025.
После округления имеем х1 = -1,35003. Как нетрудно видеть, найденные значения неизвестных имеют мало общего с истинными значениями решения х» = О, г~ = 1, хз — — 1. В чем же причина появления такой значительной погрешности? Говорить о накоплении ошибок округления не приходится, так как всего было выполнено 28 арифметических операций и лишь в 4 случаях потребовалось округление. Предположение о плохой обусловленности системы не подтверждается; вычис— ление соп»1 (А) дает значение»з 100. В действительности причина состоит в использовании на 2-м шаге мЬлого ведущего элемента а'з> = 0.0001. Следствием этого стало появление большого 22 142 разрядов мантиссы приходим к уравнению (5.41). О б р а т н ы й х о д.
Из уравнения (5.41) находим хз»з 1.00001. Сравнение с истинным значением хз — — 1 показывает, что эта величина получена с очень высокой для используемой ЭВМ точностью. Дальнейшие вычисления дают множителя узы и существенное возрастание коэффициента в последнем уравне- нии системы. Таким образом, изложенный выше вариант метода Гаусса (схема единственного деления) оказался некорректным и, следовательно, непригодным для вычислений на ЭВМ. Этот метод может привести к аварийному останову (если аЦ" = 0 при некотором «), и вычисления по нему могут оказаться неустойчивыми.
2. Метод Гаусса с выбором главного злавзеззта но столбцу (схзвза частичного выбора). О п и с а н и е м е то д а. На з-м шаге прямого хода коэффициенты уравнений системы с номерами 1 = Й + 1, ..., гп преобразуются по формулам а';~~' = еф"- ра«ф~', Ь~-1~ 5~1-~~ рН,Ц1-~~ з' = ~+ 1, ..., пз. (5.42) Интуитивно ясно, что во избежание сильного роста коэффициентов системы и связанных с этим ошибок нельзя допускать появления больших множителей и;~. В методе Гаусса с выбором главного элемента по столбцу гарантируется, что ~рд,~ ~ 1 для всех Й = 1, 2, ..., т — 1 и з = Й + 1, , зп. Отличие этого варианта метода Гаусса от схемы единственного деления заключается в том, что на Й-и шаге исключения в качестве главного элемента выбирают максимальный по модулю коэффициент а, ~ 'ь' при неизвестной зь в уравнениях с номерами з = й, й + 1, ..., пз.
Затем соответствующее выбранному коэффициенту уравнение с номером ц, меняют местами с Й-и уравнением системы для того, чтобы главный элемент занял место коэффициента аД " . После этой перестановки исключение неизвестного хь производят, как в схеме единственного деления. Пример 5.9. Решим систему уравнений (5.39) методом Гаусса с выбором главного элемента по столбцу на 6-разрядной десятичной ЭВМ. П р я м о й х о д.
1-й ш а г. Максимальный в первом столбце элемент матрицы находится в первой строке, поэтому перестановка уравнений не нужна. Здесь 1-й шаг проводится точно так же, как и в примере 5.8. 2-й ш а г. Среди элементов а<з~> = 0.0001 и еД' = 3.5 матрицы системы (5.40) максимальный принадлежит третьему уравнению. Меняя местами второе и третье уравнения, получим систему 2з1 — 9з~ + 5зз = -4, 3.5хг — 10зз = -6.5, 0.0001хд + Ззз — 3.
0001. После вычисления ><зз — 0.0001/3.5 и 2.85714 ° 10 з последнее уравнение системы преобразуется к виду 3.00029лз = 3.00029. О б р а т н ы й х о д. Из последнего уравнения находим хз —— 1. Далее, имеем хг = (-6.5 + 10хз)/3 5 = 1, х> = (-4 + 9хг — 5хз)/2 = ( 4 + 9 5)/2 = = О. В данном случае ответ получился точным. Заметим, что дополнительная работа по выбору главных элементов в схеме частичного выбора требует порядка тз действий, что практически не влияет на общую трудоемкость метода. Вычислительная устойчивость схемы час— т и ч н о г о в ы б о р а.
Детальное исследование метода Гаусса показывает, что действительной причиной неустойчивости схемы единственного деления является возможность неограниченного роста элементов промежуточных матриц А'<', А<з>, ..., А<м '> в процессе прямого хода. Так как на 1-м шаге схемы частичного выбора ~«<ь~ '( 1, то для вычисленных по формулам (5.42) элементов а<.1<> справедлива оценка 1> (а< "> ~ ( ~ а<« '> ~ + ~ а~>г» ~. Следовательно, максимальное по модулю <э <э .> 6(х*) ( /(т) сон<15(А) ° 6м. (5.43) Здесь х* — вычисленное на ЭВМ решение системы; о(х*) = 1х — х*1з/1х1 з — его относительная погрешность; соп<1е(А) = 1А1ь1А >1е — число обусловленности матрицы А; ем — машинное эпсилон; наконец, /(т) = С (т) <о(т), причем С (т) — некоторая медленно растущая функция, зависящая от порядка т системы (типа степенной функции с небольшим показателем), 1о(ти) — коэффициент роста.
Наличие в оценке (5.43) множителя 1о(т) = 2" ' указывает на то, что при большом т схема частичного выбора может оказаться плохо обусловленной и возможна существенная потеря точности. Однако практика матричных вычислений показывает, что существенный рост элементов матрицы происходит крайне редко. В подавляющем большинстве случаев действительное значение коэффициента роста не превышает 8 — 10.
Если система хорошо обусловлена, то погрешность вычисленного решения оказывается, как правило, малой. Иногда для проверки качества приближенного решения х' вычис- 144 значение элементов матрицы возрастает на одном шаге не более чем в 2 раза и в самом неблагоприятном случае т — 1 шаг прямого хода даст коэффициент роста <о(т) = 2»». Гарантия ограниченности роста элементов матрицы делает схему частичного выбора вычислительно устойчивой. Более того, для нее оказывается справедливой следующая оценка погрешности: 11 г12 ~ У(тп) 1А1е ~х12 ям~ (5.44) где 1" (т) то же, что и в оценке (5.43).
Заметим, что в неравенство (5.44) не входит число обусловленности. 3. Метод Гаусса с выбором главного элемента по всей матрице (схема полного выбора). В этой схеме допускается нарушение естественного порядка исключения неизвестных. На 1-м шаге метода среди элементов а; определяют максимальный по модулю элемент а,1, Первое уравнение системы и уравнение с '1 1 номером 11 меняют местами, Далее стандартным образом производят исключение неизвестного х.
из всех уравнений, кроме первого. На 1с-м шаге метода среди коэффициентов а1.х" при неизвестных в 1Я уравнениях системы с номерами 1 = Й, ..., т выбирают максимальный по модулю коэффициент а'~.11. Затем х-е уравнение и уравнение, 1Ас содержащее найденный коэффициент, меняют местами и исключают неизвестное х из уравнений с номерами 1 = Й+ 1, ..., т. ~/с На этапе обратного хода неизвестные вычисляют в следующем порядке: х., х,, х .
т я-1 1 Пример 5.10 Решим систему (5.39), используя схему полного выбора на 6- разрядной десятичной ЭВМ. П р я м о й х о д. 1 — й ш а г. Максимальный по модулю элемент а12 — -9 содержится в первом уравнении, поэтому перестановка уравнений не нужна. Исключаем неизвестное х2 из второго и третьего уравнений, и используя множители р21 = -5.3999/( — 9) ~ 0.599989 и 1зз1 = -1/(-9) ~ 0.111111. В результате получим систему 2х1 — 9х2 + 5хЗ = -4 2.2 10 зх1 + 3 00006хз = 3 00006 0.777778х1 — 8.05556хз = -8 05556. 2-й ш а г. Среди коэффициентов при неизвестных во втором и третьем уравнениях максимальным является коэффициент а'1' = — 8.05556.
Перестав- зз 145 ляют невязку г = Ь вЂ” Ах' и о степени близости приближенного решения к точному пытаются судить по тому, насколько мала невязка. Этот метод ненадежен по отношению к схеме частичного выбора, так как известно, что она гарантированно дает малые невязки. Более точно это утверждение можно сформулировать так: справедлива оцен- ка ляя местами второе и третье уравнения и исключая неизвестное ха (соответст- вующий множитель,из~ = 3.00006/(-8.05556) и -0.372421), приходим к системе 2х1 — 9ха + 5~ = -4, О.
777778 х1 — 8.05556ха. = -8 05556 О. 289683х1 = 2.89240-10 7. О б р а т н ы й х о д. Из последнего уравнения находим х1 = 2.89240.10 7/0.289683 В 9.98470 10 ~. Далее, имеем хз = ( — 8.05556 — 0.777778х1)/( — 8.05556) п 1.00000, л~ = (-4 — 2х1 — 5хз)/( — 9) = 1.00000. Округляя найденные значения до пяти цифр после десятичной точки, получим ответ: х1 = 0.00000, х~ = 1.00000, ха = 1.00000. Заметим, что в данном случае получено решение, совпадающее с точным.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
