Главная страница Случайная страница Разделы сайта АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Метод Гаусса.
В методе Гаусса линейная система решается в два этапа. На первом этапе система преобразуется к виду (см. рис. 2.1) , Рис. 2.1. Структура системы и портрет ее ненулевых элементов до (а) и после (б) прямого хода Гаусса
где – верхняя треугольная матрица с единичной диагональю (это так называемый прямой ход Гаусса). На втором этапе (обратный ход Гаусса) решается система . Рассмотрим эти этапы подробнее. Прямой ход. Прямой ход Гаусса состоит из n шагов. Первый шаг. Полагаем, что и разделим на него первое уравнение. Перепишем систему с учетом этого преобразования: Умножим первое уравнение на и вычтем его из i -го уравнения преобразованной системы: Обозначим . Получим Второй шаг. На втором шаге из системы исключается аналогичным образом: K-й шаг. Запишем общий вид преобразованной системы после k-го шага прямого хода Гаусса:
Здесь Проиллюстрируем, как меняется матрица системы в процессе прямого хода Гаусса на примере системы четвертого порядка (рис. 2.2; ненулевые элементы матрицы обозначены крестиками). Рис. 2.2. Преобразование матрицы системы 4-го порядка на прямом ходе Гаусса Оценим количество длинных операций (умножений и делений) на первом шаге прямого хода Гаусса. Преобразование первого уравнения требует n таких операций. Преобразование остальных n- 1 уравнений – n(n- 1 ) операций умножения и деления. Таким образом, первый шаг выполняется за длинных операций. Рассуждая по аналогии, нетрудно найти затраты на остальных n- 1 шагах. Суммарные затраты прямого хода Гаусса определяются в итоге рядом . Последняя оценка имеет место для n> > 1. Обратный ход. Запишем систему, решаемую на обратном ходе, в координатном виде Ее решение: Запись означает, что индекс k изменяется от значения n- 1 до 1 с шагом 1. Требуемое число длинных операций на обратном ходе Приближенная оценка справедлива для n> > 1. Общие затраты метода Гаусса: Таким образом, при больших n основные затраты в методе Гаусса приходятся на прямой ход.
|