- •Ширапов д.Ш.
- •Глава 1. Погрешности приближенных вычислений и основные теоремы ………………………………………...
- •Глава 2. Прямые методы решения систем линейных алгебраических уравнений ……………………………….
- •Глава 3. Итерационные методы решения систем линейных алгебраических уравнений ………………………..
- •Глава 4. Методы решения задач на собственные значения и собственные вектора………………………………
- •Введение
- •Глава 1. Погрешности приближенных вычислений и основные теоремы
- •Погрешности приближенных вычислений
- •Обусловленность системы линейных алгебраических уравнений
- •1.3. Основные теоремы
- •Доказательство
- •Доказательство
- •Доказательство
- •Глава 2. Прямые методы решения систем линейных алгебраических уравнений
- •2.1. Метод Гаусса
- •2.2. Метод Гаусса с выбором главного элемента
- •2.3. Алгоритм вычисления определителя матрицы
- •2.4. Алгоритм вычисления обратной матрицы
- •2.5. Метод Халецкого
- •2.6. Метод квадратных корней
- •2.7. Метод прогонки
- •Глава 3. Итерационные методы решения систем линейных алгебраических уравнений
- •3.1. Метод простой итерации
- •3.1.1. О сходимости итерационных процессов для систем линейных алгебраических уравнений
- •3.1.2. Оценки погрешности метода простой итерации
- •3.2. Метод Зейделя
- •3.3. Метод релаксации
- •3.4. Каноническая форма двухслойных итерационных методов
- •3.4.1. Каноническая форма метода простой итерации
- •3.4.2. Каноническая форма метода Зейделя
- •3.4.3. Теоремы двухслойных итерационных методов
- •3.5. Вариационно-итерационные методы
- •3.5.1. Метод минимальных невязок
- •3.5.2. Метод скорейшего спуска
- •Глава 4. Методы решения задач на собственные значения
- •4.1. Устойчивость задачи на собственные значения
- •4.2. Метод вращения Якоби
- •4.2.1. Различные варианты метода Якоби
- •4.3. Степенной метод
- •4.4. Обратный степенной метод
- •4.5. Итерационный метод
- •4.6. Методы для матриц, не принадлежащих к специальному классу
- •4.7. Обобщенная задача на собственные значения
- •4.7.1. Обобщенный метод Якоби
- •4.7.2. Метод приведения обобщенной задачи к стандартной
- •Задание № 2.2
- •Задание № 2.3
- •Задание № 2.4
- •Задание № 2.5
- •Задание № 2.6
- •Задание № 2.7
- •Задания к главе 3 Задание № 3.1
- •Задание № 3.2
- •Задания к главе 4 Тестовые примеры
- •Задание для индивидуального выполнения
- •Литература
Глава 2. Прямые методы решения систем линейных алгебраических уравнений
Итак, требуется решить систему линейных алгебраических уравнений
Ax=b. (2.1)
Заметим, что везде речь будет идти только о случае когда матрица А – квадратная, т.е. число уравнений совпадает с числом неизвестных, причем будет предполагаться, что система (2.1) имеет единственное решение.
Методы решения (2.1) можно разделить на две группы: прямые методы (в которых нахождение решения заканчивается за конечное число действий), итерационные методы (в которых находятся не само решение, а некоторая последовательность векторов х(к) такая, что ).
2.1. Метод Гаусса
Рассмотрим классический метод Гаусса [2-11]. Сначала перепишем систему (2.1) в развернутой форме
(2.2)
Пусть а110. Если а11=0, то поменяем местами первое и второе уравнения в (2.2), если а210, то поменяем местами первое и третье уравнения и т.д. Все ai1 не могут равняться нулю, так как detA0. Тогда из первого уравнения системы (2.2) будем иметь
х1+12х2+…+1nхn=1 , (2.3)
где 1j=a1j/a11 , (j>1), 1=b1/a11 .
С использованием уравнения (2.3) можно исключить х1 из всех оставшихся уравнений (2.2). В результате получим
(2.4)
где =aij-ai11j , =bi- ai11 , (i, j2).
На этом первый этап процесса исключения заканчивается. Индекс (1) в коэффициентах , показывает номер первого этапа.
Переходя к второму этапу процесса исключения разделим первое уравнение в (2.4) на при 0, тогда получим
х2+23х3+…+2nхn=2 , (2.5)
где 2j= / , (j>2), 2= / .
Далее с помощью уравнения (2.5), описанным выше способом, исключим все х2 из уравнений (2.4).
Продолжая далее, на к-ом этапе будем иметь уравнение, с помощью которого исключим к-ое неизвестное, т.е.
хк+к к+1хк+1+…+кnхn=k , (2.6)
где кj= / , (jк+1), к= / , (2.7)
= - кj , = - к , (i, jк+1). (2.8)
Собирая уравнения (2.3)-(2.6), полученных на всех этапах получим систему уравнений с верхней треугольной матрицей
х1+12х2+13х3+…+1nхn=1 ,
х2+23х3+…+2nхn=2 , (2.9)
………………………
хn=n .
Таким образом, алгоритм решения СЛАУ классическим методом Гаусса состоит из двух шагов:
первый – прямой ход.
По формулам (2.7), (2.8) вычисляются коэффициенты ij и i (i, j=1,…, n).
второй – обратный ход.
Определяются неизвестные xi по формуле (2.9), которую можно записать в виде
xi=i - , (i=n, n-1,…,1).
Определение 2.1. Элементы а11, , …, ,… называются ведущими элементами.
2.2. Метод Гаусса с выбором главного элемента
При численных вычислениях на компьютере неизбежны ошибки округления, следовательно, есть возможность прекращения выполнения алгоритма или получение неверных результатов, если знаменатели дробей на каком-то этапе окажутся равными нулю или очень маленькими числами. Этого недостатка можно избежать, если использовать метод Гаусса с выбором главного элемента [11]. Рассмотрим систему уравнений
Запишем расширенную матрицу коэффициентов
. (2.10)
Среди элементов матрицы aij выберем наибольший по модулю, который называется главным элементом. Пусть им будет элемент aij и используя его вычислим множители
mk= -akj/ aij для всех ki .
Строка с номером i матрицы М, содержащая главный элемент, называется главной строкой.
Далее, производим следующее действие: к каждой неглавной строке прибавляем главную строку, умноженную на соответствующий множитель mk для этой строки. В результате получим новую матрицу, у которой j-й столбец состоит из нулей, кроме одного элемента. Отбрасывая этот столбец и главную i-ю строку, получим новую матрицу М(1) и повторяем ту же операцию, только с новым главным элементом, после чего получим матрицу М(2) и т.д.
Таким образом, построим последовательность матриц М, М(1), М(2),…, М(n-1), последняя из которых представляет двучленную матрицу – строку, её также считаем главной строкой.
Затем объединяем в систему все главные строки, начиная с последней, входящей в матрицу М(n-1). После некоторой перестановки строк они образуют треугольную матрицу эквивалентную матрице (2.10). На этом заканчивается – прямой ход.
Решив систему с треугольной матрицей, последовательно находим все неизвестные – обратный ход.
Замечание 2.1. При работе с матрицами большого порядка выбор главного элемента может оказаться достаточно трудоемкой задачей. Поэтому на практике, в качестве главного элемента, выбирают первую строку, а.в качестве главного элемента наибольший по модулю элемент этой строки.