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

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

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

. . , G(1, n), G(2, 3), . . . , G(n − 1, n), таких чтоG(n − 1, n) · · · G(2, 3) G(1, n) · · · G(1, 3) G(1, 2) A = R— правая треугольная матрица.Формально можно сказать, что существует набор матриц вращенияG(1, 2), G(1, 3), . . . , G(1, n), G(2, 3), . . . , G(n − 1, n), таких чтоG(n − 1, n) · · · G(2, 3) G(1, n) · · · G(1, 3) G(1, 2) A = R— правая треугольная матрица.ОтсюдаA = G(1, 2)⊤ G(1, 3)⊤ · · · G(1, n)⊤ G(2, 3)⊤ · · · G(n − 1, n)⊤ R,и мы получили QR-разложение матрицы A, поскольку произведениематриц G(i, j)⊤ также является ортогональной матрицей.Использование преобразований вращения — ещё одинконструктивный способ получения QR-разложения.Технически он даже более прост, чем отражения Хаусхолдера.Использование преобразований вращения — ещё одинконструктивный способ получения QR-разложения.Технически он даже более прост, чем отражения Хаусхолдера.При его реализации организовывать полноценные матрицывращения G(k, l, θ) и матричные умножения с ними, конечно,нецелесообразно, так как большинством элементов в G(k, l, θ)являются нули.Результат умножения слева на матрицу вращения разумно находитьпутём перевычисления лишь ненулевых элементов всего двух строк.Использование преобразований вращения — ещё одинконструктивный способ получения QR-разложения.Технически он даже более прост, чем отражения Хаусхолдера.При его реализации организовывать полноценные матрицывращения G(k, l, θ) и матричные умножения с ними, конечно,нецелесообразно, так как большинством элементов в G(k, l, θ)являются нули.Результат умножения слева на матрицу вращения разумно находитьпутём перевычисления лишь ненулевых элементов всего двух строк.Для плотно заполненных матриц использование вращений в 1.5раза более трудоёмко, чем QR-разложение с помощью матрицотражения, но зато вращения более предпочтительны дляразреженных матриц из-за большей гибкости.Метод вращений для решениясистем линейных алгебраических уравненийЕсли необходимо решить систему линейных алгебраическихуравнений Ax = b, то с помощью матриц вращения выполнимприведение матрицы A к правому (верхнему) треугольному виду,одновременно применяя преобразования вращения к правой части b.Получим эквивалентную систему линейных уравнений Rx = b̃с треугольной матрицей R, которая легко решается обратнойподстановкой.Этот численный метод, очень похожий на метод Гаусса,но использующий ортогональные преобразования вращенияи отличающийся лучшей устойчивостью,называют методом вращений.Итерационные методыдля решения систем линейныхалгебраических уравненийИтерационные методы для решениясистем линейных алгебраических уравненийЗадачаНайти решение системы линейных алгебраических уравненийAx = bc квадратной неособенной матрицей A.Итерационные методы для решениясистем линейных алгебраических уравненийИтерационные методы решения уравнений и систем уравнений —это методы, порождающие последовательность приближений⋆{x(k) }∞k=0 к искомому решению x , которое получается как пределx⋆ = lim x(k) .k→∞Итерационные методы для решениясистем линейных алгебраических уравненийИтерационные методы решения уравнений и систем уравнений —это методы, порождающие последовательность приближений⋆{x(k) }∞k=0 к искомому решению x , которое получается как пределx⋆ = lim x(k) .k→∞Обычно говорят, что «итерационный метод сходится»,если к пределу сходитсяпоследовательность приближений {x(k) },конструируемая этим методом.Итерационные методы для решениясистем линейных уравненийНа практике переход к пределу по k → ∞ невозможен в силуконечности объёма вычислений, который мы можем произвести.Поэтому при реализации итерационных методов вместо x⋆ обычнодовольствуются нахождением какого-то достаточно хорошегоприближения x(k) к x⋆ .Итерационные методы для решениясистем линейных уравненийНа практике переход к пределу по k → ∞ невозможен в силуконечности объёма вычислений, который мы можем произвести.Поэтому при реализации итерационных методов вместо x⋆ обычнодовольствуются нахождением какого-то достаточно хорошегоприближения x(k) к x⋆ .Важно правильно выбрать условие остановки итераций,при котором прекращаем порождать очередные приближенияи выдаём x(k) в качестве решения.Далее мы подробно рассмотрим этот вопрос.Итерационные методы для решениясистем линейных уравненийОбщая схема итерационных методов:Итерационные методы для решениясистем линейных уравненийОбщая схема итерационных методов:выбираются одно или несколько начальных приближенийx(0) , x(1) , .

. . , x(ν) ,Итерационные методы для решениясистем линейных уравненийОбщая схема итерационных методов:выбираются одно или несколько начальных приближенийx(0) , x(1) , . . . , x(ν) ,затем по их известным значениям вычисляются последующиеприближенияx(k+1) ← Tk (x(0) , x(1) , . . . , x(k) ),k = ν, ν + 1, ν + 2, . . . ,где Tk — отображение, называемое оператором переходаили оператором шага (иногда уточняют, что k-го).Итерационные методы для решениясистем линейных уравненийИтерационный процесс называют p-шаговым, если его последующееприближение x(k+1) зависит только от p предшествующихприближений, т. е.

от x(k) , x(k−1) , . . . , x(k−p+1) .Итерационные методы для решениясистем линейных уравненийИтерационный процесс называют p-шаговым, если его последующееприближение x(k+1) зависит только от p предшествующихприближений, т. е. от x(k) , x(k−1) , . . . , x(k−p+1) .Наиболее простыми являются одношаговые итерационные методыx(k+1) ← Tk (x(k) ),k = 0, 1, 2, . . . ,в которых x(k+1) зависит лишь от значения одной предшествующейитерации x(k) .Итерационные методы для решениясистем линейных уравненийИтерационный процесс называют p-шаговым, если его последующееприближение x(k+1) зависит только от p предшествующихприближений, т. е. от x(k) , x(k−1) , .

. . , x(k−p+1) .Наиболее простыми являются одношаговые итерационные методыx(k+1) ← Tk (x(k) ),k = 0, 1, 2, . . . ,в которых x(k+1) зависит лишь от значения одной предшествующейитерации x(k) .Для начала работы одношаговых итерационных процессов нужнознать одно начальное приближение x(0) .Итерационные методы для решениясистем линейных уравненийИтерационный процесс называется стационарным,если оператор перехода Tk не зависит от номера шага k,т. е. Tk = T .Итерационный процесс называется нестационарным,если оператор перехода Tk зависит от номера шага k.Итерационные методы для решениясистем линейных уравненийЛинейным p-шаговым итерационным процессом будут называтьсяитерации, в которых оператор перехода имеет видTk (x(k) , x(k−1) , .

. . , x(k−p+1) )= C (k,k)x(k) + C (k,k−1)x(k−1) + . . . + C (k,k−p+1)x(k−p+1) + d(k)с какими-то коэффициентами C (k,k), C (k,k−1) , . . . , C (k,k−p+1) исвободным членом d(k) .Итерационные методы для решениясистем линейных уравненийЛинейным p-шаговым итерационным процессом будут называтьсяитерации, в которых оператор перехода имеет видTk (x(k) , x(k−1) , . . .

, x(k−p+1) )= C (k,k)x(k) + C (k,k−1)x(k−1) + . . . + C (k,k−p+1)x(k−p+1) + d(k)с какими-то коэффициентами C (k,k), C (k,k−1) , . . . , C (k,k−p+1) исвободным членом d(k) .В случае векторной переменной x все C (k,l) являются матрицамиподходящих размеров, а d(k) — вектор той же размерности, что и x.Матрицы C (k,l) часто называют матрицами переходарассматриваемого итерационного процесса.Итерационные методы для решениясистем линейных уравненийИтерационные методы решения уравнений и систем уравненийвозникли как уточняющие процедуры, которые позволяли занебольшое (удовлетворяющее практику) количество шаговполучить приемлемое по точности приближённое решение задачи.Итерационные методы для решениясистем линейных уравненийИтерационные методы решения уравнений и систем уравненийвозникли как уточняющие процедуры, которые позволяли занебольшое (удовлетворяющее практику) количество шаговполучить приемлемое по точности приближённое решение задачи.ОпределениеНевязка приближённого решения x̃ — это разность левой и правойчастей уравнения (системы уравнений) после подстановки в него x̃.Невязка приближённого решения x̃ системы линейныхалгебраических уравнений Ax = b — это разностьAx̃ − b.Итерационные методы для решениясистем линейных уравненийПричины, по которым для решения систем линейных уравненийитерационные методы могут оказаться более предпочтительными,чем прямые методы?.

. .Итерационные методы для решениясистем линейных уравненийПричины, по которым для решения систем линейных уравненийитерационные методы могут оказаться более предпочтительными,чем прямые методы?. . .1) Большинство итерационных методов являютсясамоисправляющимися, т. е. такими, в которых погрешность,допущенная в вычислениях, при сходимости исправляется входе итерирования и не отражается на окончательномрезультате.Итерационные методы для решениясистем линейных уравненийПричины, по которым для решения систем линейных уравненийитерационные методы могут оказаться более предпочтительными,чем прямые методы?. . .1) Большинство итерационных методов являютсясамоисправляющимися, т.

е. такими, в которых погрешность,допущенная в вычислениях, при сходимости исправляется входе итерирования и не отражается на окончательномрезультате.Прямые методы решения СЛАУ этим свойством не обладают,так как обратной связи от исходной системы не получают.Итерационные методы для решениясистем линейных уравнений2) Нередко итерационные процессы сравнительно несложнопрограммируются, так как представляют собой повторяющиесяединообразные процедуры, применяемые к последовательнымприближениям к решению.При решении СЛАУ с разреженными матрицами витерационных процессах можно легче, чем в прямых методах,учитывать структуру нулевых и ненулевых элементов матрицыи основывать на этом упрощённые формулыматрично-векторного умножения, которые существенноуменьшают общую трудоёмкость алгоритма.Итерационные методы для решениясистем линейных уравнений3) Иногда системы линейных алгебраических уравнений задаютсяв операторном виде, т.

е. так, что их матрица и правая часть невыписываются явно.Вместо этого задаётся действие такой матрицы (линейногооператора) на любой вектор, и это позволяет строить ииспользовать итерационные методы.С другой стороны, преобразования матриц таких систем,которые являются основой прямых методов решения системлинейных уравнений, очень сложны или порой простоневозможны.Итерационные методы для решениясистем линейных уравнений4) Быстро сходящиеся итерационные методы могут обеспечиватьвыигрыш по времени даже для СЛАУ общего вида, еслитребуют для практической сходимости небольшое числоитераций.Сходимость стационарныходношаговых итерационных методовРассмотрим далее стационарный одношаговый итерационныйпроцессx(k+1) ← Cx(k) + d,k = 0, 1, 2, .

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

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