Xreferat.com » Рефераты по математике » Методы решения систем линейных уравнений

Методы решения систем линейных уравнений

1. Решение системы линейных уравнений методом Гаусса


Задачи аппроксимации функции, а также множество других задач прикладной математики м вычислительной физики сводятся к задачам о решении систем линейных уравнений. Самым универсальным методом решения системы линейных уравнений является метод последовательного исключения неизвестных, называемый методом Гаусса.

Для иллюстрации смысла метода Гаусса рассмотрим систему линейных уравнений:


Методы решения систем линейных уравнений (1)


Эту систему запишем в матричном виде:


Методы решения систем линейных уравнений (2)


Как известно, обе части уравнения можно умножить на ненулевое число, а также можно из одного уравнения вычесть другое. Используя эти свойства, постараемся привести матрицу системы (2) к треугольному виду, т.е. к виду, когда ниже главной диагонали все элементы – нули. Этот этап решения называется прямым ходом.

На первом шаге прямого хода умножим первое уравнение на Методы решения систем линейных уравнений и вычтем из второго, тогда исключится переменная Методы решения систем линейных уравнений из второго уравнения. Затем, умножим первое уравнение на Методы решения систем линейных уравнений и вычтем из третьего, тогда система (2) преобразуется в систему вида:

Методы решения систем линейных уравнений (3)


На втором шаге прямого хода из третьего уравнения исключаем Методы решения систем линейных уравнений, т.е. из третьего уравнения вычитаем второе, умноженное, на Методы решения систем линейных уравнений, что приводит систему (3) к треугольному виду (4)


Методы решения систем линейных уравнений (4)


Систему (4) переписываем в привычном виде:


Методы решения систем линейных уравнений (5)


Теперь, из системы (5) можем находить решение в обратном порядке, т.е. сначала находим из третьего уравнения Методы решения систем линейных уравнений, далее, подставляя во второе уравнение, находим Методы решения систем линейных уравнений. Подставляя Методы решения систем линейных уравнений и Методы решения систем линейных уравнений в первое уравнение системы (5), находим Методы решения систем линейных уравнений. Нахождение решения Методы решения систем линейных уравнений из системы (5) называют обратным ходом.

Теперь, на основе рассмотренного примера, составим общий алгоритм метода Гаусса для системы:


Методы решения систем линейных уравнений (6)


Метод Гаусса состоит из двух этапов:

а) прямой ход – когда матрица системы (6) приводится к треугольному виду;

б) обратный ход – когда последовательно вычисляются неизвестные в обратном порядке, т.е. в последовательности: Методы решения систем линейных уравнений.

а) Прямой ход: для приведения системы (6) к треугольному виду, уравнения с ненулевыми коэффициентами при переменной Методы решения систем линейных уравнений переставляются таким образом, чтобы они были выше, чем уравнения с нулевыми коэффициентами Методы решения систем линейных уравнений. Далее, вычитаем первое уравнение, помноженное на Методы решения систем линейных уравнений, из второго уравнения, вычитаем первое уравнение, помноженное на Методы решения систем линейных уравнений, из третьего уравнения и т.д. В общем, вычитаем первое уравнение, помноженное на Методы решения систем линейных уравнений, из Методы решения систем линейных уравнений - го уравнения при Методы решения систем линейных уравнений, если Методы решения систем линейных уравнений. Вследствие этой процедуры, мы обнулили все коэффициенты при переменной Методы решения систем линейных уравнений в каждом из уравнений, начиная со второго, т.е. система (6) принимает вид:


Методы решения систем линейных уравнений (7)


Далее, применяем туже самую процедуру, для уравнений системы (7), начиная со второго уравнения, т.е. первое уравнение исключается из «игры». Теперь стараемся обнулить коэффициенты при переменной Методы решения систем линейных уравнений, начиная с третьего уравнения и т.д., пока не приведём систему к треугольному виду. Если Методы решения систем линейных уравнений, то система всегда приводима (теоретически) к треугольному виду. Общий алгоритм прямого хода можно представить в виде:


Методы решения систем линейных уравнений (8)


б) Обратный ход: Вычисляем неизвестные по формулам:


Методы решения систем линейных уравнений (9)


Замечание: для вычисления определителя системы можно использовать треугольную форму полученной матрицы, тогда определитель этой матрицы равен произведению диагональных элементов, т.е.

Методы решения систем линейных уравнений (10)


2. Метод Гаусса с выбором главного элемента


Метод Гаусса настолько универсален, что для некоторых систем получаются практически «плохие» результаты, поэтому разрабатываются различные хитрые выходы из ситуации. В случае, когда некоторые коэффициенты матрицы системы близки между собой, как известно относительные погрешности сильно возрастают при вычитании, поэтому классический метод Гаусса даёт большие погрешности. Чтобы обойти эту трудность, стараются в прямом ходе Гаусса выбрать то уравнение, у которого коэффициент при Методы решения систем линейных уравнений максимален и в качестве основного «игрока» выбирают именно это уравнение, тем самым обходя трудности вычитания близких чисел (если это возможно). Далее, когда нужно обнулить все коэффициенты переменной Методы решения систем линейных уравнений, кроме одного уравнения – этим особым уравнением опять выбирают то уравнение, у которого коэффициент при Методы решения систем линейных уравнений максимальный и т.д., пока не получим треугольную матрицу.

Обратный ход происходит так же, как и в классическом методе Гаусса.


3. Оценка погрешности при решении системы линейных уравнений


Для того, чтобы оценить погрешности вычислений решения системы линейных уравнений, нам нужно ввести понятия соответствующих норм матриц.

Прежде всего, вспомним три наиболее часто употребляемые нормы для вектора Методы решения систем линейных уравнений:


Методы решения систем линейных уравнений (11)


Методы решения систем линейных уравнений(Евклидова норма) (12)


Методы решения систем линейных уравнений(Чебышевская норма) (13)


Для всякой нормы векторов можно ввести соответствующую норму матриц:


Методы решения систем линейных уравнений (14)


которая согласована с нормой векторов в том смысле, что


Методы решения систем линейных уравнений (15)


Можно показать, что для трёх приведённых выше случаев нормы матрицы Методы решения систем линейных уравнений задаются формулами:

Методы решения систем линейных уравнений (16)


Методы решения систем линейных уравнений (17)


Методы решения систем линейных уравнений (18)


Здесь Методы решения систем линейных уравнений - являются сингулярными числами матрицы Методы решения систем линейных уравнений, т.е. это положительные значения квадратных корней Методы решения систем линейных уравнений - матрицы Методы решения систем линейных уравнений (которая является положительно-определённой матрицей, при Методы решения систем линейных уравнений).

Для вещественных симметричных матриц Методы решения систем линейных уравнений - где Методы решения систем линейных уравнений - собственные числа матрицы Методы решения систем линейных уравнений.

Абсолютная погрешность решения системы:


Методы решения систем линейных уравнений (19)


где Методы решения систем линейных уравнений - матрица системы, Методы решения систем линейных уравнений - матрица правых частей, оценивается нормой:


Методы решения систем линейных уравнений (20)


Относительная погрешность оценивается по формуле:


Методы решения систем линейных уравнений (21)


где Методы решения систем линейных уравнений.

4. Итерационные методы решения систем линейных уравнений


Рассмотрим систему линейных уравнений, которая плохо решается методами Гаусса. Перепишем систему уравнений в виде:


Методы решения систем линейных уравнений (22)


где Методы решения систем линейных уравнений - заданная числовая матрица Методы решения систем линейных уравнений-го порядка, Методы решения систем линейных уравнений - заданный постоянный вектор.


4.1 Метод простой итерации Якоби


Этот метод состоит в следующем: выбирается произвольный вектор Методы решения систем линейных уравнений (начальное приближение) и строится итерационная последовательность векторов по формуле:


Методы решения систем линейных уравнений, Методы решения систем линейных уравнений (23)


Приведём теорему, дающую достаточное условие сходимости метода Якоби.

Теорема. Если Методы решения систем линейных уравнений, то система уравнений (22) имеет единственное решение Методы решения систем линейных уравнений и итерации (23) сходятся к решению.

Легко заметить, что эта теорема является простым обобщением теоремы о сжатых отображениях изученных нами раньше для одношагового итерационного процесса в общем виде. Все оценки, полученные ранее, переносятся и для системы уравнений, разница лишь в понятиях соответствующих норм. Обобщая метод простой итерации Якоби для случая системы уравнений:

Методы решения систем линейных уравнений (24)


Строим алгоритм решения:

а) переписываем уравнение (24) в однородном виде и умножаем на постоянную Методы решения систем линейных уравнений - которую далее найдём из условий сходимости итерационного процесса:


Методы решения систем линейных уравнений (25)


б) добавляем Методы решения систем линейных уравнений к обеим частям (25) и получаем:


Методы решения систем линейных уравнений (26)


в) строим итерационную формулу Якоби:


Методы решения систем линейных уравнений (27)


где постоянную Методы решения систем линейных уравнений находим из условий сходимости итерационного процесса (27), который в данном случае имеет вид:


Методы решения систем линейных уравнений (28)


где Методы решения систем линейных уравнений - вектор-функция из (26) или исходя из теоремы о сжатых отображениях Методы решения систем линейных уравнений, где Методы решения систем линейных уравнений - единичная матрица.

Рассмотрим числовой пример:

Пусть имеем систему уравнений:

Методы решения систем линейных уравнений


Переписываем систему в виде:


Методы решения систем линейных уравнений


Составляем итерационную формулу:


Методы решения систем линейных уравнений


Коэффициент Методы решения систем линейных уравнений выбираем из условий: Методы решения систем линейных уравнений, т.е.


Методы решения систем линейных уравнений

Методы решения систем линейных уравнений.


4.2 Метод Гаусса-Зейделя


Для решения линейной системы уравнений разработано множество итерационных методов. Тем более, что метод простой итерации Якоби сходится медленно. Одним из таких методов является метод Гаусса-Зейделя.

Для иллюстрации метода рассмотрим числовой пример:

Методы решения систем линейных уравнений (29)


Уравнения переписаны таким образом, что на главной диагонали стоят максимальные для каждого уравнения коэффициенты.

Начинаем с приближения Методы решения систем линейных уравнений. Используя первое уравнение, находим для Методы решения систем линейных уравнений новое значение Методы решения систем линейных уравнений при условии Методы решения систем линейных уравнений.


Методы решения систем линейных уравнений (30)


Беря это значение Методы решения систем линейных уравнений и Методы решения систем линейных уравнений из второго уравнения, находим Методы решения систем линейных уравнений, далее из третьего уравнения находим Методы решения систем линейных уравнений, Методы решения систем линейных уравнений. Эти три величины дают новое приближение и можно повторить цикл с начала, получаем: Методы решения систем линейных уравнений, Методы решения систем линейных уравнений, Методы решения систем линейных уравнений и т.д. Итерации продолжаются до выполнения неравенства Методы решения систем линейных уравнений.

Общий алгоритм метода Гаусса-Зейделя имеет вид:

Пусть


Методы решения систем линейных уравнений (31)


где у матрицы Методы решения систем линейных уравнений - все диагональные элементы отличны от нуля, т.е. Методы решения систем линейных уравнений (если Методы решения систем линейных уравнений, тогда переставляем строки так, чтобы добиться условия Методы решения систем линейных уравнений). Если Методы решения систем линейных уравнений-ое уравнение системы (31) разделить на Методы решения систем линейных уравнений, а затем все неизвестные кроме Методы решения систем линейных уравнений - перенести в правую часть, то мы придём к эквивалентной системе вида:

Методы решения систем линейных уравнений (32)


где Методы решения систем линейных уравнений, Методы решения систем линейных уравнений, Методы решения систем линейных уравнений


Методы решения систем линейных уравнений (33)


Метод Гаусса-Зейделя состоит в том, что итерации производятся по формуле:


Методы решения систем линейных уравнений (34)


где Методы решения систем линейных уравнений - номер итерации, а Методы решения систем линейных уравнений.

Замечание: для сходимости метода (34) достаточно выполнения хотя бы одного из условий:

а)


Методы решения систем линейных уравнений, Методы решения систем линейных уравнений (35)


б) Методы решения систем линейных уравнений - симметричная и положительно-определённая матрица.


5. Решение системы линейных уравнений методом Ритца


Если Методы решения систем линейных уравнений - симметричная и положительно-определённая матрица, то задача решения линейной системы уравнений:


Методы решения систем линейных уравнений (36)


эквивалентна задаче нахождения точки минимума функции многих переменных:


Методы решения
    <div class=

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.
Подробнее

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: