Лекция 4 СЛАУ. Решение систем линейных алгебраических уравнений. Методы простой итерации и итерации Зейделя. Метод прогонки a x
 Скачать 3.58 Mb.
|
|
Лекция 4 Решение систем линейных алгебраических уравнений. Методы простой итерации и итерации Зейделя. Метод прогонки. a x a x a x b a x a x a x b a x a x a x b n n n n n n nn n n 11 1 12 2 1 1 21 1 22 2 2 2 1 1 2 2 где a ij - коэффициенты перед неизвестными уравнений, x i - неизвестные величины, b i - свободные члены уравнений. система линейных алгебраических уравнений Определение Решением системы линейных алгебраических уравнений являются те значения неизвестных, при которых все уравнения системы обращаются в тождество прямые итерационные Гаусса, Крамера, Жордана, окаймления, ортогонализации, главных элементов, метод квадратного корня, метод прогонки метод итерации, метод итерации Зейделя Методы решения систем линейных алгебраических уравнений Прямые методы дают решение за конечное число действий, просты и универсальны. Решение реализуют в два шага: систему преобразуют к более простому виду, затем решают упрощенную систему и получают решение. Итерационные методы привлекают простотой реализации, требуют задания начального приближения, применяются для решения систем специального вида. Скорость сходимости итерационного процесса зависит от свойств матрицы коэффициентов перед неизвестными и выбора начального приближения Метод простой итерации (метод последовательных приближений) Позволяет найти приближенное решение системы линейных алгебраических уравнений с заданной точностью ε Условия сходимости метода Все коэффициенты a ii отличны от нуля и справедливы неравенства n j i j ij ii a a 1 Метод простой итерации Перепишем уравнения системы в виде 1 1 2 2 1 1 1 2 3 23 1 21 21 22 2 1 3 13 2 12 1 11 1 1 1 1 n nn n n n nn n n n n n x a x a x a b a x x a x a x a b a x x a x a x a b a x Возьмем приближенное решение системы x 1 0 , x 2 0 , x 3 0 ,... x n 0 – нулевое приближение, подставим в формулы и вычислим первое приближение x 1 1 , x 2 1 , x 3 1 ,... x n 1 ) 0 ( 1 1 ) 0 ( 2 2 ) 0 ( 1 1 1 ) 1 ( ) 0 ( 2 ) 0 ( 3 23 ) 0 ( 1 21 21 22 ) 1 ( 2 ) 0 ( 1 ) 0 ( 3 13 ) 0 ( 2 12 1 11 ) 1 ( 1 1 1 1 n nn n n n nn n n n n n x a x a x a b a x x a x a x a b a x x a x a x a b a x подставим x 1 1 , x 2 1 , x 3 1 ,... x n 1 в формулы и вычислим второе приближение x 1 2 , x 2 2 , x 3 2 ,... x n 2 . Повторяем вычисления до выполнения условия достижения точности для всех x i ) 1 ( ) ( max k i k i x x Задание Имеется система линейных алгебраических уравнений . Найти решение системы методом итерации с точностью 10 -3 . 8 12 3 18 6 32 5 83 5 18 2 15 5 3 20 4 3 2 4 3 2 1 4 2 1 4 3 2 1 x x x x x x x x x x x x x x проверка условия сходимости • Первое уравнение 20 сравниваем с суммой 1+1+3+5 условие справедливо • Второе уравнение 18 сравниваем с суммой 2+5 условие справедливо • Третье уравнение 32 сравниваем с суммой 1+5+6 условие справедливо • Четвертое уравнение 12 сравниваем с суммой 3+2 условие справедливо. n j i j ij ii a a 1 Перепишем уравнения системы в виде ) 0 ( 3 ) 0 ( 2 ) 1 ( 4 ) 0 ( 4 ) 0 ( 2 ) 0 ( 1 ) 1 ( 3 ) 0 ( 4 ) 0 ( 1 ) 1 ( 2 ) 0 ( 4 ) 0 ( 3 ) 0 ( 2 ) 1 ( 1 3 8 12 1 6 5 18 32 1 5 2 83 18 1 5 3 15 20 1 x x x x x x x x x x x x x x Решение в Microsoft Excel. Занесение в ячейки таблицы нулевого приближения Вычисление первого приближения Получение следующих приближений копированием формул Режим отображения формул Решение в MathCAD методом Гаусса с использованием функции lsolve 1. Задать матрицу коэффициентов перед неизвестными системы 2. Задать столбец свободных членов системы 3. Написать имя функции с аргументами 4. Нажать знак равенства для вывода решения lsolve Решение в MathCAD методом итерации с использованием функции find функция Find позволяет находить Значения корней нелинейных уравнений решения системы линейных алгебраических уравнений решения системы линейных уравнений •Задание начальных приближений (нулевых): x:=x 0 , y:=y 0 , z:=z 0 ,… •Ввод слова Given, указывающего на то, что далее следует система уравнений •Ввод системы уравнений; (знак равенства ставится «жирный» с палитры «логический» •Ввод функции Find(x,y,z,…) •Получение решения нажатием клавиши =. Реализация функции find find Метод итерации Зейделя В методе простой итерации при вычислении следующего приближения используются значения предыдущего. В методе Зейделя предложено при получении следующего приближения использовать не только значения предыдущего шага итерации, но и уже полученные значения текущей итерации Формулы итерации Зейделя ) 1 ( 1 1 ) 1 ( 2 2 ) 1 ( 1 1 ) 1 ( ) 0 ( 2 ) 0 ( 3 23 ) 1 ( 1 21 2 22 ) 1 ( 2 ) 0 ( 1 ) 0 ( 3 13 ) 0 ( 2 12 1 11 ) 1 ( 1 1 1 1 n nn n n n nn n n n n n x a x a x a b a x x a x a x a b a x x a x a x a b a x Метод Зейделя Точность вычислений достигнута Режим отображения формул Метод прогонки a x a x a x b a x a x a x b a x a x a x b n n n n n n nn n n 11 1 12 2 1 1 21 1 22 2 2 2 1 1 2 2 Метод Гаусса заключается в приведении матрицы коэффициентов перед неизвестными к треугольному виду Прямой ход метода Гаусса n n nn n n n n b x a b x a x a b x a x a x a 2 2 2 22 1 1 2 12 1 11 Обратный ход метода Гаусса n n b x n n n n n x a b x 1 1 Метод прогонки – метод Гаусса для систем специального вида: матрица коэффициентов трехдиагонального вида (n=4) 4 4 4 3 4 3 4 3 3 3 2 3 2 3 2 2 2 1 2 1 2 1 1 1 f x b x a f x c x b x a f x c x b x a f x c x b Прямой ход метода прогонки Как в прямом ходе метода Гаусса, мы достигаем треугольного вида матрицы коэффициентов умножением всех элементов строки на число и вычитанием ее из нижестоящей строки системы. Результат прямого хода прогонки 4 4 3 4 3 3 2 3 2 2 1 2 1 1 g x g x s x g x s x g x s x 1 1 1 b c s 1 i i i i i s a b c s 1 1 1 b f g 1 1 i i i i i i i s a b g a f g i=2, 3, 4 Получение ответа обратным ходом прогонки по формулам 4 4 g x 1 i i i i x s g x i=3, 2, 1. Задание Найти решение системы методами итерации и прогонки 4 7 2 3 10 16 2 8 3 6 0 3 5 4 5 4 3 4 3 2 3 2 1 2 1 x x x x x x x x x x x x x Решение методом прогонки 4 7 2 3 10 16 2 8 3 6 0 33 , 0 5 4 5 4 3 4 3 2 3 2 1 2 1 x x x x x x x x x x x x x Систему приводим к виду, когда коэффициент в первом уравнении перед первой неизвестной равняется единице Решение в Microsoft Excel занесение исходных данных Выполнение прямого хода Формулы прямого хода Выполнение обратного хода Решение в режиме отображения формул Сопоставление с решением методом итерации Преобразуем уравнения системы применения метода итерации 7 4 10 3 2 8 2 16 6 3 33 , 0 4 5 5 3 4 4 2 3 3 1 2 2 1 x x x x x x x x x x x x x Решение методом итерации Прогонка в пакете Mathcad На практике часто приходится сталкиваться не только с системами линейных алгебраических уравнений с квадратной матрицей А, но и с прямоугольной матрицей размера MxN, т. е. системами, в которых число неизвестных не равно числу уравнений (как больше, так и меньше него). Такие системы для решения требуют специфического подхода. Неклассические системы Рассмотренные выше системы предполагают равно количество уравнений и неизвестных. Это означает, что матрица из коэффициентов перед неизвестными (А) квадратная. Для таких систем доказано, что решение существует и единственно, если определитель матрицы отличен от нуля (│А│≠0). Плохо обусловленная система – система, у которой определитель отличен от нуля, но очень близок к нулю. Несмотря на то, что плохо обусловленные системы имеют единственное решение, на практике искать их чаще всего не имеет смысла 5 01 6 3 3 2 y x y x 5 6 3 3 01 2 y x y x и • Переопределенные системы линейных алгебраических уравнений – системы, в которых число уравнений больше числа неизвестных • Недоопределенные системы линейных алгебраических уравнений – системы, в которых число уравнений меньше числа неизвестных Переопределенные и недоопределенные системы линейных алгебраических уравнений |