1611688847-5b7354cc83380cb6c671f7c9dd5f83f8 (826648), страница 8

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 8)

.U =.. .. ..  ,. . .. ... ×× ×. .×× × ··· × ×00Первая матрица называется верхней (или правой) треугольнойматрицей, а вторая — нижней (или левой) треугольной матрицей.Треугольными называются системы линейных алгебраическихуравнений, матрицы которых имеют треугольный вид.Решение треугольных линейных системРассмотрим линейную систему уравненийLx = bс неособенной нижней треугольной матрицей L = (lij ), так чтоlij = 0 при j > i и lii 6= 0 для всех i = 1, 2, . . . , n.Решение треугольных линейных системРассмотрим линейную систему уравненийLx = bс неособенной нижней треугольной матрицей L = (lij ), так чтоlij = 0 при j > i и lii 6= 0 для всех i = 1, 2, .

. . , n.Её первое уравнение содержит только одну неизвестнуюпеременную x1 , второе уравнение содержит две неизвестных и т. д.,так что в i-е уравнение входят лишь переменные x1 , x2 , . . . , xi .Решение треугольных линейных системРассмотрим линейную систему уравненийLx = bс неособенной нижней треугольной матрицей L = (lij ), так чтоlij = 0 при j > i и lii 6= 0 для всех i = 1, 2, . . . , n.Её первое уравнение содержит только одну неизвестнуюпеременную x1 , второе уравнение содержит две неизвестных и т.

д.,так что в i-е уравнение входят лишь переменные x1 , x2 , . . . , xi .Найдём из первого уравнения значение x1 и подставим его вовторое уравнение системы, в котором в результате останется всегоодна неизвестная переменная x2 .Вычислим x2 и затем подставим известные значения x1 и x2 втретье уравнение, из которого определится x3 . И так далее.Решение треугольных линейных системОписанной алгоритм соответствует следующему псевдокоду:DO FOR i = 1 TO n.Xlij xj  liix i ←  bi −j<iEND DO.Решение треугольных линейных системОписанной алгоритм соответствует следующему псевдокоду:DO FOR i = 1 TO n.Xlij xj  liix i ←  bi −.j<iEND DOЭтот процесс называется прямой подстановкой, посколькувыполняется по возрастанию индексов компонент вектора x,и в нём на очередном шаге выполняется подстановкауже найденных значений неизвестных в следующее уравнение.Решение треугольных линейных системДля решения систем линейных уравнений U x = b c неособеннойверхней треугольной матрицей U = ( uij ) существует аналогичныйпроцесс, который называется обратной подстановкой — он идёт вобратном направлении, т.

е. от xn к x1 .Решение треугольных линейных системДля решения систем линейных уравнений U x = b c неособеннойверхней треугольной матрицей U = ( uij ) существует аналогичныйпроцесс, который называется обратной подстановкой — он идёт вобратном направлении, т. е. от xn к x1 .Его псевдокод имеет следующий вид:DO FOR i = n DOWNTO 1.Xuij xj  uiix i ←  bi −j>iEND DO.Вычислительные методыанализа и линейной алгебрыКурс лекцийС.П. ШарыйКафедра математического моделирования НГУЛекция 29 ноября 2017 г.Метод Гаусса для решениялинейных систем уравненийМетод Гаусса для решения систем линейных алгебраическихуравнений впервые в новом времени был описан К.Ф.

Гауссом в1849 году, хотя письменные источники свидетельствуют о том, чтоего знали как минимум за 250 лет до нашей эры.Метод Гаусса для решениялинейных систем уравненийМетод Гаусса для решения систем линейных алгебраическихуравнений впервые в новом времени был описан К.Ф. Гауссом в1849 году, хотя письменные источники свидетельствуют о том, чтоего знали как минимум за 250 лет до нашей эры.Известно, чтоумножение какого-либо уравнения системы на ненулевое число,замена уравнения на его сумму с другим уравнением системыприводят к равносильной системе уравнений, т.

е. имеющей те жесамые решения.Воспользуемся этими свойствами для преобразования системылинейных алгебраических уравнений к более простому виду.Метод Гаусса для решениялинейных систем уравненийПусть дана система линейных алгебраических уравнений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.Метод Гаусса для решениялинейных систем уравненийПусть дана система линейных алгебраических уравнений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-м уравнением системы.Проделаем подобное преобразование с остальными — 3-м, 4-м и т. д.до n-го уравнениями системы, т.

е. будем умножать первоеуравнение на (−ai1 /a11 ) и складывать с i-м уравнением системы.В результате получим равносильную исходной систему линейныхалгебраических уравнений, в которой неизвестная переменная x1присутствует лишь в первом уравнении.Матрица получившейся системы станет выглядеть следующимобразом:a11 × × · · · × 0× × ··· × . ... .. × ×. 0 ...... ........  .× × ··· ×0В преобразованной системе уравнения со 2-го по n-е образуютквадратную подсистему размера (n−1) × (n−1), в которойнеизвестная x1 уже не присутствует.Её можно решать отдельно, никак не обращаясь к первомууравнению исходной системы.В преобразованной системе уравнения со 2-го по n-е образуютквадратную подсистему размера (n−1) × (n−1), в которойнеизвестная x1 уже не присутствует.Её можно решать отдельно, никак не обращаясь к первомууравнению исходной системы.Если элемент на месте (2, 2) не сделался равным нулю, к этойсистеме можно заново применить вышеописанную процедуруисключения неизвестных.В преобразованной системе уравнения со 2-го по n-е образуютквадратную подсистему размера (n−1) × (n−1), в которойнеизвестная x1 уже не присутствует.Её можно решать отдельно, никак не обращаясь к первомууравнению исходной системы.Если элемент на месте (2, 2) не сделался равным нулю, к этойсистеме можно заново применить вышеописанную процедуруисключения неизвестных.Её результатом будет обнуление поддиагональных элементов2-го столбца матрицы СЛАУ.И так далее.В преобразованной системе уравнения со 2-го по n-е образуютквадратную подсистему размера (n−1) × (n−1), в которойнеизвестная x1 уже не присутствует.Её можно решать отдельно, никак не обращаясь к первомууравнению исходной системы.Если элемент на месте (2, 2) не сделался равным нулю, к этойсистеме можно заново применить вышеописанную процедуруисключения неизвестных.Её результатом будет обнуление поддиагональных элементов2-го столбца матрицы СЛАУ.И так далее.Выполнив (n − 1) шагов подобного процесса — для 1-го, 2-го,.

. . , (n − 1)-го столбцов матрицы данной системы, получимлинейную систему с верхней треугольной матрицей, котораярешается с помощью обратной подстановки.Преобразование системы линейных алгебраических уравнений кравносильному треугольному виду называется прямым ходомметода Гаусса. Его псевдокод —DO FOR j = 1 TO n − 1DO FOR i = j + 1 TO nrij ← (−aij /ajj )DO FOR k = j TO naik ← aik + rij ajkEND DObi ← bi + rij bjEND DOEND DOДалее следует обратный ход метода Гаусса для решенияполученной верхней треугольной системы.Он является процессом «обратной подстановки»:DO FOR i = n DOWNTO 1.Xx i ←  bi −aij xj  aiij>iEND DOМетод Гаусса для систем линейных уравненийМожно ли представитьвыполнение метода Гауссадля решения систем линейных уравненийв матричном виде?Матричная интерпретация метода ГауссаУмножение первого уравнения системы на ri1 = −ai1 /a11 исложение его с i-ым уравнением можно представить в матричномвиде как умножение обеих частей системы Ax = b слева на матрицу1 0 .. . ri1 .. .001...1011.Она отличается от единичной матрицыодним дополнительным ненулевым элементом ri1 на месте (i, 1).Исключение поддиагональных элементов первого столбца матрицы— это последовательное домножение обеих частей системы Ax = bслева на матрицы11 01 r21 1. r....031,. 0, . ....1.101010000и так далее до10...100rn10...11.Умножение матриц выписанного выше вида выполняетсяпо простому правилу: 11 1 1.... ri1 .. · 11 .....r.  k111000011 ri1= rk10...10...1.Это правило также верно в случае, когда у матриц-сомножителейв первом столбце присутствует более одного ненулевого элемента.Следовательно, обнуление поддиагональных элементов первогостолбца и соответствующие преобразования правой части в методеГаусса — это умножение обеих частей системы слева на матрицуE1 = 10r21 1r31 0...rn110...1.Аналогично, обнуление поддиагональных элементов j-го столбцаматрицы системы линейных уравнений и соответствующиепреобразования правой части можно интерпретировать какумножение системы слева на матрицуEj = 1..0.10rj+1,j 1...rnj...1.Матричная интерпретация метода ГауссаВ целом метод Гаусса — это последовательность умножений обеихчастей решаемой системы слева на матрицы Ej выписанного вышевида, j = 1, 2, .

. . , n − 1.В результате матрицей системы становитсяEn−1 · · · E2 E1 A = U,которая является верхней треугольной матрицей.Матричная интерпретация метода ГауссаВ целом метод Гаусса — это последовательность умножений обеихчастей решаемой системы слева на матрицы Ej выписанного вышевида, j = 1, 2, . . . , n − 1.В результате матрицей системы становитсяEn−1 · · · E2 E1 A = U,которая является верхней треугольной матрицей.Так как все Ej — нижние треугольные матрицы, их произведениетакже является нижним треугольным.Кроме того, все Ej неособенны, det Ej 6= 0, так как это нижниетреугольные матрицы с единицами по главной диагонали.Как следствие, произведение En−1 · · · E2 E1 также неособенно(невырождено), т.

е.det En−1 · · · E2 E1 6= 0.Как следствие, произведение En−1 · · · E2 E1 также неособенно(невырождено), т. е.det En−1 · · · E2 E1 6= 0.Если определитьL = En−1 · · · E2 E1−1,то L — тоже нижняя треугольная матрица с единицами по главнойдиагонали.Как следствие, произведение En−1 · · · E2 E1 также неособенно(невырождено), т. е.det En−1 · · · E2 E1 6= 0.Если определитьL = En−1 · · · E2 E1−1,то L — тоже нижняя треугольная матрица с единицами по главнойдиагонали.Как следствие, для матрицы A справедливо равенствоA = LUКак следствие, произведение En−1 · · · E2 E1 также неособенно(невырождено), т.

Характеристики

Список файлов лекций