Д.П. Костомаров, А.П. Фаворский - Вводные лекции по численным методам (pdf) (1113729), страница 2
Текст из файла (страница 2)
Чтобы найти решение системы (1), нужно подсчитать n + 1определитель. Это можно сделать за конечное число арифметических операций.Однако с точки зрения практики важное значение имеет фактическое числонеобходимых операций. Здесь нас и поджидает главная трудность. Определитель n ого порядка – это n ! слагаемых, каждое из которых является произведением n чисел.Таким образом, для его вычисления нужно выполнить ( n − 1) n ! умножений и n !сложений – всего Qn = n ⋅ n ! арифметических операций. Оценим это число.
При n 1число n ! можно подсчитать с помощью асимптотической формулы Стирлинга:nn3n⎞⎛n⎞2 ⎛n ! ≈ 2π n ⎜ ⎟ , так что Qn ≈ 2π ⋅ n ⎜ ⎟ .⎝e⎠⎝e⎠При умеренном значении n = 20 эта формула дает астрономическое число:Q20 ≈ 5 ⋅ 1019 .Компьютеру, производительность которого составляет m операций/сек, длявычисления определителя двадцатого порядка понадобится времяT20 ≈ (5 ⋅ 1019 / m) сек.В частности, при m = 1010 операций/сек получимT20 ≈ 5 ⋅ 109 сек.
≈ 170 лет.Даже увеличение производительности компьютера на два, три порядка не спасаетположения.Такие результаты получены при n = 20 , в то время, как в современныхприкладных задачах приходится решать системы с n = 106 и более уравнений. Изпроведенного анализа ясно, что рассчитывать решение СЛАУ по формулам Крамера свычислением определителей «в лоб» невозможно, т. е.
практическая ценность этихформул невелика.1.2. Метод Гаусса.Блестящий конструктивный выход из критической ситуации, описанной выше,дает метод Гаусса. Этот метод удобно условно разделить на два этапа. На первомэтапе (прямой ход) система (1) приводится к треугольному виду. Затем на второмэтапе (обратный ход) осуществляется последовательное отыскание неизвестныхx1 ,K, xn из этой треугольной системы.Перейдем к подробному описанию метода Гаусса. Не ограничивая общности,будем считать, что коэффициент a11 , который называют ведущим элементом первогошага, отличен от нуля (в случае a11 = 0 поменяем местами уравнения с номерами 1 и i ,-3при котором ai1 ≠ 0 ; поскольку система предполагается невырожденной, то такойномер i заведомо найдется).Разделим все члены первого уравнения на a11 и введем в качестве новыхкоэффициентов c1i , i = 2,K n и правой части y1 отношенияaaafc12 = 12 , c13 = 13 , K c1n = 1n , y1 = 1 .(7)a11a11a11a11Вычтем из каждого i -го уравнения системы ( i = 2,K , n ) первое уравнениеумноженное на ai1 .
Проделав это, мы исключим неизвестное x1 из всех уравнений,кроме первого. Преобразованная таким образом система (1) примет эквивалентныйвид:x1 + c12 x2 + c13 x3 + K + c1n xn = y1(1)(1)a22x2 + a23x3 + K + a2(1)n xn = f 2(1)KKKKKKKKKKKKK.(8)(1)an(1)2 x2 + an(1)3 x3 + K + annxn = f n(1)Значения новых коэффициентов и правых частей системы (8) вычисляются поформулам:afaij(1) = aij − ai1 1 j , f i (1) = f i − ai1 1 .(9)a11a11Естественно выделить из (8) «укороченную» систему, содержащую n − 1 уравнение(1)(1)a22x2 + a23x3 + K + a2(1)n xn = f 2(1)(1)(1)a32x2 + a33x3 + K + a3(1)n xn = f 3(1)KKKKKKKKKKKKK(1)an(1)2 x2 + an(1)3 x3 + K + annxn = f n(1) .Продолжая далее процесс исключения, после ( n − 1) шага редуцируем исходнуюсистему к виду:x1 + c12 x2 + c13 x3 + K + c1n xn = y1x2 + c23 x3 + K + c2 n xn = y2KKKKKKKKKKKKKKxn−1 + cn −1,n xn = yn−1(10)xn = y nили в матричной формеCx = y ,где матрица C является верхней треугольной матрицей с единицами на главнойдиагонали-4-⎡1 c12 c13 K c1n ⎤⎢0 1 c K c ⎥232n⎥.(11)C=⎢MMM ⎥⎢M M⎢0 00 K 1 ⎥⎦⎣Построение системы (10) завершает прямой ход метода Гаусса.Обратный ход состоит в последовательном определении неизвестных из системы(10) в обратном порядке:xn = y nxn −1 = yn −1 − cn−1,n xnxn −2 = yn−2 − cn −2,n−1 xn −1 − cn−2,n xnKKKKKKKKKKKK(12)x1 = y1 − c12 x2 − c13 x3 − K − c1n xnПодсчитаем число арифметических операций, которое требуется выполнить прирешении СЛАУ по методу Гаусса.
Первый шаг прямого хода, согласно формулам (7) и(9), требует n делений и n ( n − 1) сложений и умножений. Мы учитываем деленияотдельно, поскольку для компьютера, как и для человека, это более сложная операция.Переходя последовательно от n к ( n − 1) , потом от ( n − 1) к ( n − 2 ) и т.д. подсчитаемобщее число арифметических операций на стадии прямого хода. Оно включаетделений1Q1 = n + ( n − 1) + L + 1 = n ( n + 1) ,(13)2сложений и умножений1Q2 = n ( n − 1) + ( n − 1)( n − 2 ) + L + 2 ⋅ 1 = n ( n 2 − 1) .(14)3Обратный ход, согласно формулам (12), вообще не требует деления, а необходимоечисло сложений и умножений подсчитывается по формуле1(15)Q3 = 1 + 2 + L + ( n − 1) = n ( n − 1) .2Сравнивая (13) и (14) с (15), мы видим, что обратный ход существенно прощепрямого.
Сумма (14) и (15) дает общее число сложений и умножений, необходимоедля решения СЛАУ по методу Гаусса:15⎞ 1⎛Q = Q2 + Q3 = n ( n − 1) ⎜ n + ⎟ = n 3 + O ( n 2 ) .(16)32⎠ 3⎝Оно не идет ни в какое сравнение с числом n ⋅ n ! , которое требуют формулы Крамерапри прямом вычислении определителей.Описанная выше процедура решения системы (1) методом Гаусса можетоказаться неустойчивой по отношению к случайным ошибкам, которые неизбежныпри компьютерных расчетах в результате округления чисел из-за конечной длинымашинного слова. Действительно, предположим, что в процессе приведения системы(1) к треугольному виду (10) у матрицы C (11) образовались большие по модулю-5элементы: ci , j > 1 и даже ci , j1 .
Тогда при вычислении неизвестных по формулам(12) во время обратного хода умножение найденных с ошибками округления чисел xiна большие по модулю элементы матрицы C приведет к увеличению этих ошибок.Наоборот, если матрица C оказалась такой, что все ее элементы удовлетворяютусловиюci , j ≤ 1 ,(17)то роль ошибок округления в процессе вычислений будет нивелироваться.Опишем, как можно добиться выполнения условия (17).
Приступая к первомушагу прямого хода метода Гаусса, рассмотрим элементы a1, j первой строки матрицыA и найдем среди них элемент наибольший по модулю. Пусть он имеет номер j1 .Поменяем в системе (1) первый столбец и столбец с номером j1 местами, изменивсоответствующим образом нумерацию неизвестных. В результате такой процедурынаибольший по модулю элемент первой строки станет ведущим элементом первогошага a1,1 . Благодаря этому элементы c1, j первой строки матрицы C , которыерассчитываются по формулам (7), будут удовлетворять неравенству (17).Процедуру выделения наибольшего по модулю элемента в очередной строке ипревращения его в ведущий элемент нужно затем повторять во время каждого шагапрямого хода метода Гаусса.
В этом случае все элементы ci , j треугольной матрицы C(11) будут удовлетворять неравенствам (17), обеспечивая устойчивость метода поотношению к ошибкам округления, Такой способ коррекции называется выборомведущего элемента по строке.Поясним важность специального выбора ведущего элемента в каждой строке вовремя прямого хода метода Гаусса на простом примере. Рассмотрим систему трехуравнений с тремя неизвестными1.2357 x1 + 2.1742 x2 − 5.4834 x3 = −2.07353.4873x1 + 6.1365 x2 − 4.7483x3 = 4.8755(18)6.0696 x1 − 6.2163x2 − 4.6921x3 = −4.8388.Легко проверить, что ее решение имеет видx1 = x2 = x3 = 1 .(19)Решим систему (18) с помощью метода Гаусса, не обращая внимание на величиныэлементов матрицы. Все результаты расчетов условимся представлять в виде чисел сплавающей запятой с пятью значащими цифрами.
Тогда после прямого хода получимсистему треугольного вида:x1 + 1.7595 x2 − 4.4375 x3 = −1.6780x2 + 15324 x3 = 15324(20)x3 = 0.99992.Значение x3 = 0.99992 выглядит вполне приемлемым. Однако для двух другихнеизвестных мы получим следующие значения: x2 = 2 , x1 = −0.75990 . Причинаслучившегося заключается в потере точности при вычислении x2 из-за больших-6значений коэффициента c23 и правой части y2 треугольной системы (20), которыевычислены с ошибками вследствие отбрасывания "лишних" значащих цифр.Теперь воспользуемся процедурой выбора главного элемента по строке. Для этогов данном случае достаточно поменять местами первый и третий столбцы матрицысистемы. В результате система примет вид:−5.4834 x3 + 2.1742 x2 + 1.2357 x1 = −2.0735−4.7483x3 + 6.1365 x2 + 3.4873x1 = 4.8755 .(21)−4.6921x3 − 6.2163x2 + 6.0696 x1 = −4.8388При такой ее записи ведущим элементом первого шага становится число −5.4834 .
Оноявляется наибольшим по модулю элементом первой строки системы (21). Теперьприменение метода Гаусса приводит к следующей системе с треугольной матрицей:x3 − 0.39651x2 − 0.22535 x1 = 0.37814x2 + 0.56827 x1 = 1.5682 .(22)x1 = 0.99995Все ее элементы удовлетворяют неравенству (17). Осуществляя обратный ход,получим решение системы:x1 = 0.99995 , x2 = 0.99996 , x3 = 0.99999 .(23)Полученные значения неизвестных xi хорошо согласуются с ответом (19) в рамкахпринятой точности вычислений.Нетрудно предвидеть, что при бесконтрольном применении метода Гаусса длярешения больших систем ( n >> 1 ) возможностей для потери точности становится ещебольше, в то время как выполнение процедуры выбора ведущих элементов по строкамснимает эту проблему.В заключение отметим, что первый этап метода Гаусса может быть использовандля вычисления определителя матрицы A . Прямой ход метода Гаусса основан намногократном выполнении операции сложения одной из строк матрицы с другойстрокой, взятой с некоторым множителем, что не меняет определителя.
Следует лишьучесть, что при делении ведущей строки на ее диагональный элемент определительтакже делится на этот элемент. Кроме того, иногда приходится переставлять столбцыпри выборе главного элемента по строке. Поскольку определитель приведеннойтреугольной системы (матрицы C ) всегда равен единице, то определитель ∆исходной системы равен(1)( n −1),∆ = det A = (−1) k a11a22...annгде k – число перестановок столбцов в процессе редукции матрицы A к треугольнойматрице C .1.3. Системы с диагональным преобладанием.Определение.Назовем систему (1) системой с диагональным преобладанием по строке, еслиэлементы матрицы A (2) удовлетворяют неравенствам:-7nai ,i > ∑ ai , j , 1 ≤ i ≤ n(24)j =1j ≠iНеравенства (24) означают, что в каждой строке матрицы A диагональный элементвыделен: его модуль больше суммы модулей всех остальных элементов той же строки.ТеоремаСистема с диагональным преобладанием всегда разрешима и притом единственнымобразом.Рассмотрим соответствующую однородную систему:n∑aj =1i, jxj = 0, 1≤ j ≤ n(25)Предположим, что она имеет нетривиальное решение x j , Пусть наибольшая помодулю компонента этого решения соответствует индексу j = k , т.
е.x k > 0 , xk ≥ x j , 1 ≤ j ≤ n .(26)Запишем k -ое уравнение системы (25) в видеna k ,k xk = − ∑ a k , j x jj =1j ≠kи возьмем модуль от обеих частей этого равенства. В результате получим:nak ,k xk ≤ ∑ ak , j x j ≤ xkj =1j ≠kn∑aj =1j ≠kk, j.(27)Сокращая неравенство (27) на множитель xk , который, согласно (26), не равен нулю,придем к противоречию с неравенством (24), выражающим диагональноепреобладание. Полученное противоречие позволяет последовательно высказать триутверждения:1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
