1611688890-f641c9ec8276824e4686da772eb56520 (826652), страница 47
Текст из файла (страница 47)
Например, решение нелинейныхуравнений или систем уравнений часто сводится к последовательностирешений линейных уравнений (см. метод Ньютона в Главе 4).Следует отметить, что системы линейных алгебраических уравнений не всегда предъявляются к решению в каноническом виде (3.48).Это придаёт дополнительную специфику процессу решения подобныхзадач и иногда диктует выбор тех или иных методов решения.Пример 3.6.1 Пусть в R2 задана область D = [x1 , x1 ] × [x2 , x2 ], имеющая форму прямоугольника со сторонами, параллельными координатным осям. Рассмотрим в ней численное решение дифференциальногоуравнения Лапласа∂2u ∂2u+ 2 =0(3.50)∂x21∂x2для функции двух переменных u = u(x1 , x2 ).Уравнением Лапласа описывается, к примеру, распределение температуры стационарного теплового поля, потенциал электростатическогополя или же потенциальное течение несжимаемой жидкости. Для определения конкретного решения этого уравнения задают ещё какие-либокраевые условия на границе расчётной области.
Мы будем считать заданными значения искомой функции u(x1 , x2 ) на границе прямоугольника:u(x1 , x2 ) = f (x2 ),u(x1 , x2 ) = f (x2 ),(3.51)u(x1 , x2 ) = g(x1 ),u(x1 , x2 ) = g(x1 ).(3.52)Рассматриваемую задачу определения функции u(x1 , x2 ), которая удовлетворяет уравнению (3.50) внутри области и условиям (3.51)–(3.52)на границе, называют задачей Дирихле для уравнения Лапласа.Станем решать задачу (3.50)–(3.52) с помощью конечно-разностногометода, в котором искомая функция заменяется своим дискретныманалогом, а производные в решаемом уравнении заменяются на разностные отношения. Введём на области D равномерную прямоугольную сетку, и вместо функции u(x1 , x2 ) непрерывного аргумента будемрассматривать её значения в узлах построенной сетки (см. Рис. 3.12).2843.
Численные методы линейной алгебрыРис. 3.12. Расчётная область и сетка для численногорешения уравнения Лапласа (3.50).Если обозначить через uij значение искомой функции u в точке xij , топосле замены вторых производных формулами (2.67) получим системусоотношений видаui−1,j − 2uij + ui+1,jui,j−1 − 2uij + ui,j+1+= 0,h21h22(3.53)i = 1, 2, . . .
, m − 1, j = 1, 2, . . . , n − 1, для внутренних узлов расчётнойобласти. На границе области имеем условияui0 = f i ,uin = f i ,(3.54)u0j = g j ,umj = g j ,(3.55)где i = 1, 2, . . . , m − 1, j = 1, 2, . . . , n − 1, а f i , f i , g i , gi — значенияфункций f , f , g, g в соответствующих узлах.Соотношения (3.53) и (3.51)–(3.52) образуют, очевидно, систему линейных алгебраических уравнений относительно неизвестных uij , i =1, 2, . .
. , m − 1, j = 1, 2, . . . , n − 1, но она не имеет канонический вид(3.48), так как неизвестные имеют двойные индексы. Конкретный вид(3.48), который получит решаемая система уравнений, зависит от способа выбора базиса в пространстве векторов неизвестных, в частности,от способа перенумерации этих неизвестных, при котором мы образуемиз них вектор с элементами, имеющими один индекс.Ясно, что рассмотренный пример может быть сделан ещё более выразительным в трёхмерном случае, когда нам необходимо численно решать трёхмерное уравнение Лапласа.3.6.
Прямые методы решения линейных систем285Системы линейных алгебраических уравнений, аналогичные рассмотренной в Примере 3.6.1, где матрица и вектор неизвестных не заданы в явном виде, будем называть системами в операторной форме.Не все из изложенных ниже методов решения СЛАУ могут быть непосредственно применены к системам подобного вида.По характеру вычислительного алгоритма методы решения уравнений и систем уравнений традиционно разделяют на прямые и итерационные.
В прямых методах искомое решение получается в результатевыполнения конечной последовательности действий, так что эти методы нередко называют ещё конечными или даже точными. Напротив, витерационных методах решение достигается как предел некоторой последовательности приближений, которая конструируется по решаемойсистеме уравнений.Одна из основных идей, лежащих в основе прямых методов длярешения систем линейных алгебраических уравнений, состоит в том,чтобы эквивалентными преобразованиями привести решаемую системук наиболее простому виду, из которого решение находится уже непосредственно. В качестве простейших могут выступать системы с диагональными, двухдиагональными, треугольными и т. п.
матрицами. Чемменьше ненулевых элементов остаётся в матрице преобразованной системы, тем проще и устойчивее её решение, но, с другой стороны, темсложнее и неустойчивее приведение к такому виду. На практике обычно стремятся к компромиссу между этими взаимно противоположнымитребованиями, и в зависимости от целей, преследуемых при решенииСЛАУ, приводят её к диагональному (метод Гаусса-Йордана), двухдиагональному (см., к примеру, [65]) или треугольному виду. Мы, в основном, рассмотрим методы, основанные на приведении к треугольномувиду.Наконец, для простоты мы далее подробно разбираем случай системуравнений (3.48)–(3.49), в которых число неизвестных n равно числууравнений m, т. е.
имеющих квадратную n×n-матрицу коэффициентов.3.6аРешение треугольных линейных системНапомним, что треугольными матрицами называют матрицы, укоторых все элементы ниже главной диагонали либо все элементы выше главной диагонали нулевые (так что и нулевые, и ненулевые эле-2863. Численные методы линейной алгебрыменты образуют× ××U =0треугольники):··· × ×... × ×.. ....,.
..× ××××L = ×...×××...×0......××···,×где крестиками «×» обозначены ненулевые элементы. В первом случае говорят о верхней (или правой) треугольной матрице, а во втором— о нижней (или левой) треугольной матрице. Соответственно, треугольными называются системы линейных алгебраических уравнений,матрицы которых имеют треугольный вид — верхний или нижний.Рассмотрим для определённости линейную систему уравнений(3.56)Lx = bс неособенной нижней треугольной матрицей L = (lij ), так что lij = 0при j > i и lii 6= 0 для всех i = 1, 2, .
. . , n. Её первое уравнение содержиттолько одну неизвестную переменную x1 , второе уравнение содержитдве неизвестных переменных x1 и x2 , и т. д., так что в i-е уравнениевходят лишь переменные x1 , x2 , . . . , xi . Найдём из первого уравнениязначение x1 и подставим его во второе уравнение системы, в котором врезультате останется всего одна неизвестная переменная x2 . Вычислимx2 и затем подставим известные значения x1 и x2 в третье уравнение,из которого определится x3 . И так далее.Описанной выше последовательности действий соответствует следующий простой алгоритм решения линейной системы (3.56) с нижнейтреугольной n × n-матрицей:DO FOR i = 1 TO n.Xlij xj liixi ← bi −j<iEND DO.(3.57)2873.6.
Прямые методы решения линейных системОн позволяет последовательно друг за другом вычислить искомые значения неизвестных переменных, начиная с первой. Этот процесс называется прямой подстановкой, поскольку выполняется по возрастаниюиндексов компонент вектора x и его главным содержанием являетсяподстановка, на очередном шаге, уже найденных значений неизвестных в следующее уравнение.Для решения систем линейных уравнений U x = b c неособеннойверхней треугольной матрицей U = ( uij ) существует аналогичный процесс, который называется обратной подстановкой — он идёт в обратном направлении, т. е. от xn к x1 .
Его псевдокод имеет слудующий вид:DO FOR i = n DOWNTO 1.Xuij xj uiixi ← bi −.(3.58)j>iEND DO3.6бМетод Гаусса для решениялинейных систем уравненийОписываемый в этом разделе метод Гаусса для решения систем линейных алгебраических уравнений впервые в новом времени был описан К.Ф. Гауссом в 1849 году, хотя письменные источники свидетельствуют о том, что он был известен как минимум за 250 лет до нашейэры.Хорошо известно, что умножение какого-либо уравнения системына ненулевое число, а также замена уравнения на его сумму с другимуравнением системы приводят к равносильной системе уравнений, т. е.имеющей те же самые решения.
Воспользуемся этими свойствами дляпреобразования решаемой системы линейных алгебраических уравнений к более простому виду.2883. Численные методы линейной алгебрыПусть дана система линейных алгебраических уравненийa11 x1 + a12 x2 + . . . + a1n xn = b1 , a21 x1 + a22 x2 + . . . + a2n xn = b2 ,...............an1 x1 + an2 x2 + . . . + amn xn = bm ,в которой коэффициент a11 — ненулевой, т.
е. a11 6= 0. Умножим первоеуравнение системы на (−a21 /a11 ) и сложим со вторым уравнением. Врезультате коэффициент a21 во втором уравнении занулится, а получившаяся система будет совершенно равносильна исходной.Проделаем подобное преобразование с остальными — 3-м, 4-м и т. д.до n-го уравнениями системы, т. е. будем умножать первое уравнениена (−ai1 /a11 ) и складывать с i-ым уравнением системы.
В результате получим равносильную исходной систему линейных алгебраическихуравнений, в которой неизвестная переменная x1 присутствует лишьв первом уравнении. Матрица получившейся СЛАУ станет выглядетьследующим образом:a11××···×0××···......···×...0...0×...××...×,.. . ×где посредством «×» обозначены элементы, возможно, не равные нулю.Рассмотрим теперь в преобразованной системе уравнения со 2-го поn-е.
Они образуют квадратную подсистему линейных уравнений размера (n−1) × (n−1), в которой неизвестная переменная x1 уже не присутствует и которую можно решать отдельно, никак не обращаясь кпервому уравнению исходной системы. Если элемент на месте (2, 2) несделался равным нулю, к этой системе можно заново применить вышеописанную процедуру исключения неизвестных. Её результатом будетобнуление поддиагональных элементов 2-го столбца матрицы СЛАУ.
Итак далее.Выполнив (n − 1) шагов подобного процесса — для 1-го, 2-го, . . . ,(n − 1)-го столбцов матрицы данной системы, мы получим, в конце2893.6. Прямые методы решения линейных системконцов, линейную систему с верхней треугольной матрицей, котораянесложно решается с помощью обратной подстановки, рассмотреннойвыше в §3.6а. Описанное преобразование системы линейных алгебраических уравнений к равносильному треугольному виду называетсяпрямым ходом метода Гаусса, и его псевдокод выглядит следующимобразом:DO FOR j = 1 TO n − 1DO FOR i = j + 1 TO nrij ← (−aij /ajj )DO FOR k = j TO naik ← aik + rij ajk(3.59)END DObi ← bi + rij bjEND DOEND DOОн выражает процесс последовательного обнуления поддиагональныхэлементов j-го столбца матрицы системы, j = 1, 2, .
. . , n − 1, и соответствующие преобразования вектора правой части. Матрица системы приэтом приводится к верхнему треугольному виду. Далее следует обратный ход метода Гаусса для решения полученной верхней треугольнойсистемы, и он является процессом обратной подстановки из §3.6а:DO FOR i = n DOWNTO 1.Xaij xj aiixi ← bi −,(3.60)j>iEND DOОн позволяет последовательно вычислить, в обратном порядке, искомые значения неизвестных, начиная с n-ой. Отметим, что в псевдокоде2903.
Численные методы линейной алгебры(3.59) прямого хода метода Гаусса зануление поддиагональных элементов первых столбцов уже учтено нижней границей внутреннего циклапо k, которая равна j.Помимо изложенной выше вычислительной схемы существует много других версий метода Гаусса. Весьма популярной является, к примеру, схема единственного деления. При выполнении её прямого ходасначала делят первое уравнение системы на a11 6= 0, что даётx1 +a1nb1a12x2 + · · · +xn =.a11a11a11(3.61)Умножая затем уравнение (3.61) на ai1 , вычитают результат из i-гоуравнения системы для i = 2, 3, .
. . , n, добиваясь обнуления поддиагональных элементов первого столбца. Затем процедура повторяется вотношении 2-го уравнения и 2-го столбца получившейся СЛАУ, и такдалее. Обратный ход для решения окончательной верхней треугольнойсистемы совпадает с (3.60).Схема единственного деления совершенно эквивалентна алгоритму(3.59) и отличается от него лишь тем, что для каждого столбца деление в ней выполняется действительно только один раз, тогда каквсе остальные операции — это умножение и сложение. С другой стороны, уравнения преобразуемой системы в схеме единственного делениядополнительно масштабируются диагональными коэффициентами принеизвестных, и в некоторых случаях это бывает нежелательно.3.6вМатричная интерпретация метода ГауссаУмножение первого уравнения системы на ri1 = −ai1 /a11 и сложение его с i-ым уравнением могут быть представлены в матричном видекак умножение обеих частей системы Ax = b слева на матрицу1 0 .. . r i1 .. .001...1011,2913.6.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
