Лабораторная работа № 1. Лабораторная работа Решение систем линейных уравнений 5 Решение систем линейных уравнений. Общие положения
 Скачать 357.99 Kb.
|
|
Лабораторная работа № 3. Решение систем линейных уравнений 2.5 Решение систем линейных уравнений. Общие положения. Решение систем линейных уравнений является одной из задач, наиболее часто встречающихся на практике, и может быть найдено различными методами (нужно также сказать, что многие задачи в конечном счете сводятся к решению систем линейных уравнений). Напоминаем, что решить систему линейных уравнений значит найти совокупность чисел (значений неизвестных) которые при подстановке в каждое уравнение системы вместо соответствующих неизвестных обращают его в тождество. Такая совокупность чисел называется решением системы. Система, для которой существует хоть одно решение, называется совместной. Как известно, совместная система, имеющая единственное решение, называется определенной, совместная же система, имеющая сколько угодно решений, называется неопределенной, а система, не имеющая ни одного решения, называется несовместной. Пусть дана система линейных уравнений с неизвестными: (2.6) или в векторно-матричной форме: где – квадратная матрица, содержащая строк и столбцов, и заданный и искомый -компонентные векторы. Предположим, что эта система не вырождена, т.е. ее определитель отличен от нуля: В этом случае она имеет единственное решение, которое может быть записано с помощью формул Крамера: здесь , матрица получается из матрицы заменой -го столбца столбцом правых частей : Хотя формулы Крамера дают решение системы в явном виде, с вычислительной точки зрения они неэффективны. Расчет по ним требует слишком большого числа операций и оказывается очень чувствительным к ошибкам округления. Поэтому для решения систем линейных уравнений используются другие методы, которые по принципам организации вычислений можно разделить на два класса: прямые (точные) и итерационные (приближенные). Прямыми методами называются такие методы, которые позволяют за конечное число действий получить точное решение системы (например, метод последовательного исключения неизвестных метод Гаусса относится к прямым методам, и этот метод подробно будет рассмотрен ниже). Итерационные методы, как уже отмечалось выше, дают приближенное решение системы с заданной точностью. Точное решение теоретически может быть получено как результат бесконечного процесса. Для решения систем алгебраических уравнений можно использовать итерационные методы, которые позволяют определить вектор неизвестных как предел бесконечной последовательности векторов , вычисляемых некоторым единообразным процессом, называемым процессом итерации. Вычислительные схемы итерационных методов просты для реализации на компьютерах. Преимущества сходящихся итерационных методов по сравнению с точными заключаются в следующем: 1) Часто оказывается, что итерации сходятся быстро и позволяют получить результат с достаточной точностью, требуя для этого значительно меньшее число арифметических операций по сравнению с точными методами. 2) Случайные арифметические ошибки, допускаемые при вычислении итераций, автоматически устраняются на следующем шаге итерации, в то время как при выполнении точных методов, арифметические ошибки накапливаются. 3) Итерационные методы особенно выгодны при решении систем уравнений, имеющих большое число коэффициентов, равных нулю. Такие системы называются системами с разреженными матрицами. Одним из итерационных методов решения систем линейных алгебраических уравнений является метод Зейделя, который будет рассмотрен в этой главе. 2.6. Алгоритмы решения систем линейных уравнений а) Метод Гаусса. Метод Гаусса основан на приведении матрицы системы к треугольному виду. Это достигается последовательным исключением неизвестных из уравнений системы. Сначала с помощью первого уравнения исключается из второго и всех последующих уравнений системы. Затем с помощью второго уравнения исключается из третьего и всех последующих уравнений. Этот процесс продолжается до тех пор, пока в левой части последнего (n-го) уравнения не останется лишь один член с неизвестным , т. е. матрица системы будет приведена к треугольному виду. Этот процесс называется прямым ходом метода Гаусса. Заметим, что к такому виду приводится лишь невырожденная матрица, т. е. определитель матрицы отличен от нуля. В противном случае метод Гаусса неприменим. Обратный ход метода Гаусса состоит в последовательном вычислении искомых неизвестных: решая последнее уравнение, находим ; далее, используя это значение, из предпоследнего уравнения вычисляем и т.д. Последним будет найден из первого уравнения. Проиллюстрируем метод Гаусса на примере решения системы из трех линейных уравнений; в этом случае (то есть для n = 3) система (2.6) запишется в следующем виде: , (2.7) , (2.8) (2.9) Предполагается, что . Если это не так, необходимо переставить уравнения (2.7) (2.9) таким образом, чтобы в первом уравнении коэффициент при не был равен нулю. Решение будем выполнять поэтапно, обозначая каждый этап через k k = 1 i = 2. Определим множитель для уравнения (2.8). Умножим первое уравнение (2.7) на множитель и вычтем из второго: (2.10) Используя обозначения , , и учитывая, что в уравнении (2.10) коэффициент при равен нулю (так как, подставляя выражение для c, получаем ) уравнение (2.8) запишется в следующем виде: i = 3. Определим множитель и выполним ту же самую процедуру для третьего уравнения (2.9) c использованием соответствующих обозначений, тогда искомая система (2.7) (2.9) примет следующий вид: , (2.7 ¢ ) , (2.8 ¢ ) (2.9 ¢ ) Как видим, остается преобразовать последнее уравнение в системе (2.7 ¢ ) (2.9 ¢ ) для приведения системы к треугольному виду; поэтому переходим к следующему этапу. k = 2 i = 3. По схеме, аналогичной для случая k = 2, вводим множитель , умножаем второе уравнение (2.8 ¢ ) на множитель и вычитаем из третьего и, используя соответствующие обозначения и учитывая, что коэффициент при в третьем уравнении равен нулю (ср. с (2.8 ¢ ) и (2.9 ¢ )), получаем окончательно треугольную матрицу для нашей системы: , (2.7 ¢¢ ) , (2.8 ¢¢ ) , (2.9 ¢¢ ) где , Очевидно, что, решая систему (2.7 ¢¢ ) (2.9 ¢¢ ), находят сначала из уравнения (2.9 ¢¢ ) и затем, подставляя его в (2.8 ¢¢ ), находят . Найденные значения и подставляют в уравнение (2.7 ¢¢ ) и определяют . Таким образом, обратный ход будет определяться формулами: , (2.11) , = (2.12) Из этого примера видно, что схему решения легко распространить для любого значения n. Прямой ход: На этапе k неизвестная исключается введением множителя , (2.13) и выполнением следующих вычислений (ср. (2.10)): (2.14) (2.15) Обратный ход. Сначала вычисляется значение неизвестной (ср. (2.11)): ; (2.16) а затем последовательно вычисляются остальные неизвестные , , , (ср. с (2.12)): , (2.17) здесь Замечание. В формулах не записывались верхние нулевые индексы (0). Отметим некоторые особенности метода Гаусса. Во-первых, алгоритм метода Гаусса достаточно прост и экономичен по числу арифметических операций, однако для его применения необходимо, чтобы все ведущие элементы были отличны от нуля. Близость ведущих элементов к нулю может привести к большой потере точности решения. В связи с этим были предложены различные варианты метода Гаусса с выбором ведущих элементов по всей матрице. Во-вторых, при применении метода Гаусса не требуется предварительного выяснения вопроса о совместности системы, так как в процессе самого выполнения придем к одному из следующих вариантов: 1) Если система совместна и определенна, то метод приводит к ее единственному решению (см. числовой пример к методу Гаусса). 2) Если система несовместна, то этот метод приводит к тому, что на каком-то этапе вместе с исключаемой неизвестной исключаются и все остальные неизвестные, а в правой части остается свободный член, отличный от нуля. 3) Если система совместная, но неопределенная, то на некотором этапе два уравнения оказываются тождественными, и таким образом, уравнений оказывается на одно меньше, чем неизвестных. Рассмотрим примеры. Пример 2.5. Решить систему На этапе k = 2 при решении этой системы методом Гаусса получаем: Здесь вместе с исключением из третьего уравнения исключается и , что приводит к противоречию, так как 0 ¹ 6. Таким образом, применив метод Гаусса, выяснили, что система, заданная в примере 2.1, несовместна (то есть имеет вариант 2). Пример 2.6. Решить систему На этапе k = 2 при решении этой системы методом Гаусса получаем: а это значит, что исходная система оказывается равносильной системе (сравни второе и третье уравнения): которая является хоть и совместной, но неопределенной (вариант 3). Пример 2.7. Решить следующую систему линейных уравнений методом Гаусса: , (П1.1) , (П1.2) (П1.3) Решение. 1) Решение выполним по алгоритму, приведенному в п. 2.4, учитывая, что n = 3. 2) Проводим прямой ход. k = 1. По формуле (2.13) вычисляем коэффициент = = 3/10 для случая i = 2 и = 5/10 для i = 3. С этими коэффициентами по формулам (2.14) и (2.15) преобразовываем уравнения (П1.2) и (П1.3) соответственно и получаем следующую систему: , (П1.1 ¢ ) , (П1.2 ¢ ) (П1.3 ¢ ) Учитывая, что коэффициент мал, переставляем уравнения (П1.2 ¢ ) и (П1.3 ¢ ) и получаем следующую систему: , (П1.1 ¢¢ ) , (П1.2 ¢¢ ) (П1.3 ¢¢ ) k = 2. По формуле (2.13) вычисляем коэффициент = = ( 0.1) / 2.5 = 0.04 для i = 3. После преобразования с этим коэффициентом по формулам (2.14) и (2.15) уравнения (П1.3 ¢¢ ) получаем систему с треугольной матрицей: , Ответ: 3) По формуле (2.16) вычисляем : 4) Остальные неизвестные вычисляем по формуле (2.17). Получаем следующие значения: = 1, = 0. б) Метод Зейделя. Метод Зейделя является одним из широко применяемых итерационных методов. Как известно, в итерационных методах строится бесконечно повторяющийся процесс и если этот процесс сходится, то на каждом его шаге получают все более и более точное приближение к искомому решению данной системы уравнений. Но прежде чем приступить к решению системы линейных уравнений методом итераций, необходимо проверить систему на сходимость, а именно, для выполнения условий сходимости итерационного процесса необходимо, чтобы диагональные элементы удовлетворяли условию: (2.18) В случае, если условие (2.18) не выполняется, то выбирают из уравнений системы такие уравнения, модули коэффициентов в которых больше суммы модулей остальных коэффициентов. Выбранные уравнения записывают так, чтобы наибольший по модулю коэффициент оказался диагональным. Остальные уравнения составляют с помощью линейной комбинации оставшихся и выбранных уравнений. Например, для системы уравнений ; (a) ; (b) ; (c) (d) условие (2.18) выполняется только для (d): =6. Преобразовать эту системе можно так. Уравнение (с) нужно сделать вторым, так как в этом случае элемент, равный 7, станет диагональным и для него будет выполняться условие (2.18): =4. Первое уравнение получаем линейной комбинацией всех четырех уравнений: 2 · c + b + + a +d, а третье как (a) (b). В итоге получаем систему уравнений , , , , у которой все диагональные элементы удовлетворяют условию (2.18). Решение систем линейных уравнений по методу Зейделя выполняется следующим образом. Сначала задают некоторый произвольный вектор , который является начальным приближением к искомому решению . Затем строят последовательность приближенных значений , k = 1, 2, 3,..., сходящихся к точному решению системы . Последовательность векторов , , . , ,... сходится к вектору ( ), если для любого > 0 существует натуральное число N , начиная с которого ( ) выполняется условие: < , где некоторое положительное число (называемое, как и в других итерационных методах, заданной точностью вычислений). в) Алгоритм метода Зейделя. Геометрическая интерпретация метода Зейделя. 1) Исходную систему линейных алгебраических уравнений (2.6) разрешают относительно неизвестных , то есть (2.19) Такое преобразование всегда выполнимо для системы, определитель которой не равен нулю, другими словами, в этом случае, при необходимости, можно так переставить уравнения системы, что при разрешении i-го уравнения относительно неизвестной найдется коэффициент . (Заметим, что в первом уравнении в правой части не содержится неизвестная , во втором и т. д., но для общего подхода запись выполняют обычно в форме (2.19)). 2) Задают начальное приближение . Начальный вектор может быть выбран произвольно, однако необходимо использовать всю имеющуюся информацию о системе уравнений. 3) В первое уравнение системы подставляют координаты вектора и вычисляют новое значение первой координаты : Используя вычисленное значение и начальные значения остальных переменных , из второго уравнения системы определяют новое значение второй координаты : Используя уже вычисленные приближения, получают значения всех остальных координат. Так, последняя координата будет иметь значение: В результате будет определено первое приближение вектора к решению системы . 4) Начальный вектор заменяют вектором и вычисляют следующее приближение. В общем случае k + 1 приближение определяют по формулам: Так как метод Зейделя итерационный, вычисления продолжаются до тех пор, пока все значения не станут близкими к . Близость этих значений можно характеризовать максимальной абсолютной величиной их разности . Тогда при заданной допустимой погрешности критерий окончания итерационного процесса можно записать в виде , (2.20) где i = 1 , ..., n . При выполнении данного условия итерационный процесс называется сходящимся, и в этом случае значения переменных стремятся к решению системы уравнений. Рассмотрим геометрическую интерпретацию метода Зейделя (см. рис. 2.9, а, 2.9, б и 2.9, в) Пусть дана система из двух уравнений с двумя неизвестными: (2.21) Решением этой системы будет точка пересечения двух прямых, заданных уравнениями системы , Проверяем систему на сходимость, то есть на выполнение условия (2.18): в первом уравнении , во втором , значит, систему можно решать методом итерации. С тем чтобы в системе (2.21) применить метод Зейделя, преобразуем ее: Сначала задаемся начальным приближением и ищем . Геометрически это соответствует точке пересечения оси абсцисс с прямой (см. рис. 2.8, а). Далее проводим прямую, параллельную оси ординат, до пересечения с прямой , получая тем самым . На этом первый шаг итерации методом Зейделя заканчивается. Дальнейшие итерации проводятся точно таким же способом для достижения условия (2.20) (последовательность итераций на рисунке 2.8, а указана стрелками). Теперь переставим местами уравнения системы (2.21) (2.22) приведем их к виду, пригодному для применения метода Зейделя: (2.23) Понятно, от перестановки местами уравнений решение системы не изменится. Установим, будет ли итерационный метод сходящимся в этом случае. Для уравнения (2.22) проверяем условие (2.18): для первого уравнения и для второго; получаем, что ни один из диагональных элементов не удовлетворяет условию (2.18), поэтому для преобразованной системы (2.23) итерационный процесс должен получиться расходящимся, что и показано на рисунке 2.9, б. Кроме случаев, которые мы рассмотрели выше, в методе Зейделя может иметь случай, когда процесс «зацикливается»; этот случай иллюстрируется на рисунке 2.9, в (последовательность итераций показана стрелками). г) Сравнение методов Гаусса и Зейделя. Кроме отмеченных выше особенностей данных 11.09.2022, 12:01 Стр. 1 из 1 |