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

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

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

е.det En−1 · · · E2 E1 6= 0.Если определитьL = En−1 · · · E2 E1−1,то L — тоже нижняя треугольная матрица с единицами по главнойдиагонали.Как следствие, для матрицы A справедливо равенствоA = LU— эта матрица представляетсяв виде произведения нижней треугольной Lи верхней треугольной U матриц.ОпределениеПредставление матрицы A в видеA = L U,где L — нижняя треугольная матрица, а U верхняя треугольнаяматрица, называют треугольным разложением матрицы илиLU-разложением.ОпределениеПредставление матрицы A в видеA = L U,где L — нижняя треугольная матрица, а U верхняя треугольнаяматрица, называют треугольным разложением матрицы илиLU-разложением.Вывод.ОпределениеПредставление матрицы A в видеA = L U,где L — нижняя треугольная матрица, а U верхняя треугольнаяматрица, называют треугольным разложением матрицы илиLU-разложением.Вывод.Преобразования матрицы A в прямом ходе метода Гаусса можнорассматривать как её разложение на нижний треугольный L иверхний треугольный U множители.Если LU-разложение матрицы A исходной СЛАУ уже дано, томожно переписать системуAx = bв равносильной формеL (U x) = b.Если LU-разложение матрицы A исходной СЛАУ уже дано, томожно переписать системуAx = bв равносильной формеL (U x) = b.Тогда её решение сводится к решению двух треугольных системлинейных алгебраических уравнений(Ly = b,Ux = yс помощью прямой и обратной подстановок соответственно.Метод Гаусса с выбором ведущего элементаИ в прямом, и в обратном ходе метода Гаусса встречаются операцииделения, которые невыполнимы, если делитель равен нулю.

Тогдане может быть выполнен и метод Гаусса в целом.Простой пример0 −1 210 3 4 5  x =  20 6 −7 830Метод Гаусса с выбором ведущего элементаИ в прямом, и в обратном ходе метода Гаусса встречаются операцииделения, которые невыполнимы, если делитель равен нулю. Тогдане может быть выполнен и метод Гаусса в целом.Простой пример0 −1 210 3 4 5  x =  20 6 −7 830Как модифицировать метод Гаусса, чтобы его можно былоприменять для решения любых систем линейных уравнений Ax = bс неособенными матрицами, т.

е. когда det A 6= 0 ?Метод Гаусса с выбором ведущего элементаОпределениеВедущим элементом в методе Гаусса называют элемент матрицырешаемой системы, на который выполняется деление приисключении поддиагональных элементов очередного столбца.Иногда его называют также главным элементом.Метод Гаусса с выбором ведущего элементаОпределениеВедущим элементом в методе Гаусса называют элемент матрицырешаемой системы, на который выполняется деление приисключении поддиагональных элементов очередного столбца.Иногда его называют также главным элементом.В алгоритме метода Гаусса, описанном выше, ведущим всюдуберётся диагональный элемент ajj , вне зависимости от его значения.Метод Гаусса с выбором ведущего элементаОпределениеВедущим элементом в методе Гаусса называют элемент матрицырешаемой системы, на который выполняется деление приисключении поддиагональных элементов очередного столбца.Иногда его называют также главным элементом.В алгоритме метода Гаусса, описанном выше, ведущим всюдуберётся диагональный элемент ajj , вне зависимости от его значения.Нужно модифицировать метод Гаусса так, чтобы ведущий элемент,по-возможности, всегда был отличен от нуля.Метод Гаусса с выбором ведущего элементаИдеяИзменение порядка уравнений в системе приводит к равносильнойсистеме уравнений, хотя при этом в матрице системыпереставляются строки и она существенно меняется.Назовём активной подматрицей j-го шага прямого хода методаГаусса подматрицу матрицы системы, образованную последнимиn − j + 1 строками и столбцами.(j −1j −1(0активнаяподматрица0j-ый столбецСтруктура матрицы системы перед началом j-го шага прямого ходаМетод Гаусса с выбором ведущего элементаОпределениеЧастичным выбором ведущего элемента на j-ом шаге прямого ходаметода Гаусса называют его выбор, как максимального по модулюэлемента из всех элементов j-го столбца, лежащих не вышедиагонали.Метод Гаусса с выбором ведущего элементаОпределениеЧастичным выбором ведущего элемента на j-ом шаге прямого ходаметода Гаусса называют его выбор, как максимального по модулюэлемента из всех элементов j-го столбца, лежащих не вышедиагонали.Частичный выбор ведущего элемента сопровождается необходимойперестановкой строк матрицы и компонент правой части (т.

е.уравнений СЛАУ).Метод Гаусса с выбором ведущего элементаОпределениеЧастичным выбором ведущего элемента на j-ом шаге прямого ходаметода Гаусса называют его выбор, как максимального по модулюэлемента из всех элементов j-го столбца, лежащих не вышедиагонали.Частичный выбор ведущего элемента сопровождается необходимойперестановкой строк матрицы и компонент правой части (т. е.уравнений СЛАУ).Именно максимальным по модулю, а не просто ненулевым,ведущий элемент выбирается для того, чтобы обеспечитьнаибольшую численную устойчивость алгоритма.Метод Гаусса с выбором ведущего элементаПредложениеМетод Гаусса с частичным выбором ведущего элемента всегдавыполним для систем линейных алгебраических уравненийс неособенными (невырожденными) квадратными матрицами.Метод Гаусса с выбором ведущего элементаПредложениеМетод Гаусса с частичным выбором ведущего элемента всегдавыполним для систем линейных алгебраических уравненийс неособенными (невырожденными) квадратными матрицами.Доказательство:Преобразования прямого хода метода Гаусса — это умножениестроки матрицы на число и сложение с другой строкой.Метод Гаусса с выбором ведущего элементаПредложениеМетод Гаусса с частичным выбором ведущего элемента всегдавыполним для систем линейных алгебраических уравненийс неособенными (невырожденными) квадратными матрицами.Доказательство:Преобразования прямого хода метода Гаусса — это умножениестроки матрицы на число и сложение с другой строкой.Cвойство определителя матрицы системы быть неравным нулюсохраняется в методе Гаусса.j −1(j −1(0активнаяподматрица0j-ый столбецСтруктура матрицы системыперед началом j-го шага прямого хода метода Гаусса.Продолжение доказательстваПеред началом j-го шага метода Гаусса эта матрица имеетблочно-треугольный вид, изображённый на рисунке.Её ненулевой определитель равенпроизведению определителей диагональных блоков.Продолжение доказательстваПеред началом j-го шага метода Гаусса эта матрица имеетблочно-треугольный вид, изображённый на рисунке.Её ненулевой определитель равенпроизведению определителей диагональных блоков.Поэтому активная подматрица имеет ненулевой определитель, т.

е.в её 1-м столбце обязан найтись хотя бы один ненулевой элемент.Продолжение доказательстваПеред началом j-го шага метода Гаусса эта матрица имеетблочно-треугольный вид, изображённый на рисунке.Её ненулевой определитель равенпроизведению определителей диагональных блоков.Поэтому активная подматрица имеет ненулевой определитель, т. е.в её 1-м столбце обязан найтись хотя бы один ненулевой элемент.Максимальный по модулю из этих ненулевых элементов такжененулевой, и его мы делаем ведущим.Как следствие, прямой ход метода Гаусса выполним.Продолжение доказательстваПеред началом j-го шага метода Гаусса эта матрица имеетблочно-треугольный вид, изображённый на рисунке.Её ненулевой определитель равенпроизведению определителей диагональных блоков.Поэтому активная подматрица имеет ненулевой определитель, т.

е.в её 1-м столбце обязан найтись хотя бы один ненулевой элемент.Максимальный по модулю из этих ненулевых элементов такжененулевой, и его мы делаем ведущим.Как следствие, прямой ход метода Гаусса выполним.Обратный ход также не встречает деления на нуль, посколькуполученная в прямом ходе верхняя треугольная матрицанеособенна, т.

е. все её диагональные элементы ненулевые.Каково матричное представление метода Гаусса с выборомведущего элемента?Каково матричное представление метода Гаусса с выборомведущего элемента?Введём элементарные матрицы1 ...0···1....P =..11···перестановок1...0...1← i-ая строка← j-ая строкакоторые получаются из единичной матрицы перестановкойдвух её строк (или столбцов) с номерами i и j.Они называются также матрицами транспозиции.Умножение на такую матрицу P слева приводит к перестановкеi-ой и j-ой строк, а умножение справа — к перестановке i-го и j-гостолбцов.Умножение на такую матрицу P слева приводит к перестановкеi-ой и j-ой строк, а умножение справа — к перестановке i-го и j-гостолбцов.Тогда для метода Гаусса с частичным выбором ведущего элементасправедливо следующее матричное представление(En−1 Pn−1 ) · · · (E1 P1 )A = U,где Ej — матрицы преобразований прямого хода метода Гаусса,P1 , P2 , .

. . , Pn−1 — элементарные матрицы перестановок,при помощи которых выполняется необходимаяперестановка строк на 1-м, 2-м, . . . , (n − 1)-м шагахпрямого хода метода Гаусса.Напомним, чтоEj = 1..0.10rj+1,j 1...rnj...1.Метод Гаусса с выбором ведущего элементаНесмотря на то, что метод Гаусса с частичным выбором ведущегоэлемента всегда выполним для систем с неособенными матрицами,на практике для некоторых «плохих» систем он всё-таки можетработать недостаточно устойчиво.Метод Гаусса с выбором ведущего элементаНесмотря на то, что метод Гаусса с частичным выбором ведущегоэлемента всегда выполним для систем с неособенными матрицами,на практике для некоторых «плохих» систем он всё-таки можетработать недостаточно устойчиво.Это происходит в случае, когда ведущий элемент оказываетсямалым, и потому коэффициенты rij из прямого метода Гауссаполучаются большими по абсолютной величине.Метод Гаусса с выбором ведущего элементаНесмотря на то, что метод Гаусса с частичным выбором ведущегоэлемента всегда выполним для систем с неособенными матрицами,на практике для некоторых «плохих» систем он всё-таки можетработать недостаточно устойчиво.Это происходит в случае, когда ведущий элемент оказываетсямалым, и потому коэффициенты rij из прямого метода Гауссаполучаются большими по абсолютной величине.По этой причине для обеспечения желаемой устойчивости методаГаусса иногда имеет смысл выбирать ведущий элемент болеетщательно, чем при частичном выборе.Метод Гаусса с полным выбором ведущего элементаЕщё один простой способ равносильного преобразования системыуравнений — перенумерация переменных.Метод Гаусса с полным выбором ведущего элементаЕщё один простой способ равносильного преобразования системыуравнений — перенумерация переменных.Ей соответствует перестановка столбцов матрицы, тогда как векторправых частей при этом неизменен.Метод Гаусса с полным выбором ведущего элементаЕщё один простой способ равносильного преобразования системыуравнений — перенумерация переменных.Ей соответствует перестановка столбцов матрицы, тогда как векторправых частей при этом неизменен.ОпределениеПолным выбором ведущего элемента называют способ его выбора,как максимального по модулю элемента из всей активнойподматрицы.При полном выборе ведущего элемента мы переставляем строки истолбцы матрицы системы и компоненты вектора правой части.Метод Гаусса с полным выбором выдущего элемента имеетследующее матричное представление(En−1 P̌n−1 ) · · · (E1 P̌1 )AP̂1 · · · P̂n−1 = U,гдеEj—матрицы преобразований прямого хода метода Гаусса,P̌i—элементарные матрицы перестановок, при помощикоторых выполняется перестановка строк,P̂j—элементарные матрицы перестановок, с помощьюкоторых выполняется перестановка столбцов.Матрицей перестановок называется матрица, которая получаетсяиз единичной матрицы перестановкой произвольного числа её строк(или столбцов).Матрица перестановок может быть представлена как произведениенескольких элементарных матриц перестановок.Матрицей перестановок называется матрица, которая получаетсяиз единичной матрицы перестановкой произвольного числа её строк(или столбцов).Матрица перестановок может быть представлена как произведениенескольких элементарных матриц перестановок.Пример.0 1 0 0 0 0 0 0 1 0 0 0 0 10 0 00 1 0 0 0 0 1 0Связь с LU-разложением матрицыТеоремаДля неособенной матрицы A существуют матрицы перестановок P̌и P̂ , такие чтоP̌ AP̂ = LU,где L, U — нижняя и верхняя треугольные матрицы, причёмдиагональными элементами в L являются единицы.

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

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