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

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

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

взять τ = τk переменным ирассмотреть итерацииx(k+1) ← x(k) − τk Ax(k) − b ,k = 0, 1, 2, . . . .Эту нестационарную версию метода простой итерации частоназывают метод Ричардсона.Л.Ф. Ричардсон, 1910 годОн, к сожалению, не смог развить удовлетворительной теориивыбора параметров τk , и для решения этого вопроса потребовалосьещё несколько десятилетий развития вычислительной математики.Можно пойти по намеченному выше пути дальше.Рассмотрим нестационарное обобщение итерационного процессаx(k+1) ← (I − ΛA) x(k) + Λb,k = 0, 1, 2, . .

. ,который получен в результате матричного предобуславливанияисходной системы линейных алгебраических уравнений.Можно пойти по намеченному выше пути дальше.Рассмотрим нестационарное обобщение итерационного процессаx(k+1) ← (I − ΛA) x(k) + Λb,k = 0, 1, 2, .

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

. . ,где {Λk }∞k=0 — некоторая последовательность матриц,выбор которой зависит от начального приближения x(0) .Нестационарные итерационные методыдля решения систем линейных уравненийДругой популярный путь построения нестационарныхитерационных методов для решения уравнений— использование вариационных принципов.Нестационарные итерационные методыдля решения систем линейных уравненийДругой популярный путь построения нестационарныхитерационных методов для решения уравнений— использование вариационных принципов.Что это такое?Термин «вариация» был введён в математику Ж.-Л. Лагранжемдля обозначения малого изменения («шевеления») независимойпеременной или рассматриваемой функции (функционала).Соответственно, метод исследования экстремумов, основанный наизучении зависимости функций от вариаций их аргументов,получил название метода вариаций.Но со временем «вариационными» стали именовать методырешения различных уравнений, которые сводят исходнуюпостановку к тем или иным задачам на нахождение экстремума.Согласно этой терминологии, вариационными принципамитеперь называют переформулировки интересующих нас задачв виде каких-либо оптимизационных задач,т.

е. задач на нахождение минимумов или максимумов.Тогда итерационные методы решения систем линейных уравнениймогут конструироваться как итерационные процессы дляотыскания этих экстремумов тех или иных функционалов.Вариационные принципы получаются весьма различнымиспособами. Некоторые из них вытекают из содержательного(физического, механического и пр.) смысла решаемой задачи.Например,в классической механике хорошо известен «принципнаименьшего действия Лагранжа»,в оптике существует «принцип Ферма».В последнее столетие имеется тенденция всё меньше связыватьвариационные принципы с конкретным физическим содержанием,они становятся абстрактным математическим инструментомрешения разнообразных задач.Как именно можно переформулировать задачу решения СЛАУ ввиде оптимизационной задачи?По-видимому, самый очевидный способ:если x⋆ — точное решение, то kAx⋆ − bk = 0,т.

е. x⋆ доставляет наименьшее возможное значениенезязки kAx − bk.Как именно можно переформулировать задачу решения СЛАУ ввиде оптимизационной задачи?По-видимому, самый очевидный способ:если x⋆ — точное решение, то kAx⋆ − bk = 0,т. е. x⋆ доставляет наименьшее возможное значениенезязки kAx − bk.Желая приобрести гладкость получаемого функционала понеизвестной переменной x, обычно берут евклидову норму невязки,или даже её квадрат, т. е. скалярное произведение hAx − b, Ax − bi,чтобы не привлекать взятия корня.ОпределениеДля заданной системы линейных алгебраических уравнений Ax = bзадача нахождения вектора x, который доставляет минимумвеличине kAx − bk22 или, что равносильно, величине kAx − bk2 ,называется линейной задачей о наименьших квадратах.ОпределениеДля заданной системы линейных алгебраических уравнений Ax = bзадача нахождения вектора x, который доставляет минимумвеличине kAx − bk22 или, что равносильно, величине kAx − bk2 ,называется линейной задачей о наименьших квадратах.Минимум kAx − bk2 может быть не равен нулю,если система уравнений Ax = b не имеет обычного решения.Это часто происходит в тех случаях, когда система Ax = bпереопределена, т.

е. когда она имеет m уравнений и n неизвестных,и m > n.ОпределениеДля заданной системы линейных алгебраических уравнений Ax = bзадача нахождения вектора x, который доставляет минимумвеличине kAx − bk22 или, что равносильно, величине kAx − bk2 ,называется линейной задачей о наименьших квадратах.Минимум kAx − bk2 может быть не равен нулю,если система уравнений Ax = b не имеет обычного решения.Это часто происходит в тех случаях, когда система Ax = bпереопределена, т. е.

когда она имеет m уравнений и n неизвестных,и m > n.Тогда вектор x, на котором достигается минимум kAx − bk2 ,называется псевдорешенем системы линейных алгебраическихуравнений Ax = b.ОпределениеДля заданной системы линейных алгебраических уравнений Ax = bзадача нахождения вектора x, который доставляет минимумвеличине kAx − bk22 или, что равносильно, величине kAx − bk2 ,называется линейной задачей о наименьших квадратах.Минимум kAx − bk2 может быть не равен нулю,если система уравнений Ax = b не имеет обычного решения.Это часто происходит в тех случаях, когда система Ax = bпереопределена, т. е.

когда она имеет m уравнений и n неизвестных,и m > n.Тогда вектор x, на котором достигается минимум kAx − bk2 ,называется псевдорешенем системы линейных алгебраическихуравнений Ax = b.Мы уже рассматривали эту задачу.Энергетическая нормаПусть A — симметричная положительно-определённая матрица.Энергетическая нормаПусть A — симметричная положительно-определённая матрица.Тогда выражение hAx, yi естьсимметричнаябилинейнаяположительно-определённая форма,т.

е. скалярное произведение векторов x и y.Энергетическая нормаПусть A — симметричная положительно-определённая матрица.Тогда выражение hAx, yi естьсимметричнаябилинейнаяположительно-определённая форма,т. е. скалярное произведение векторов x и y.Обычно обозначают его hx, yiA , то естьhx, yiA := hAx, yi.Евклидова норма (2-норма) вектора x определяется какkxk2 :=phx, xi.Евклидова норма (2-норма) вектора x определяется какkxk2 :=phx, xi.Мы определили новое скалярное произведение h·, ·iA .Далее можно определить норму вектора x, какkxkA :=phx, xiA =phAx, xi ,т. е.

как квадратный корень из произведения x на себяв этом новом скалярном произведении.ОпределениеДля заданной симетричной положительно определённойматрицы A норма k · kA называется энергетической нормойотносительно матрицы A.Нижний индекс указывает эту порождающую матрицу.Энергетическую норму k · kA часто называют также A-нормойвекторов, если в задаче имеется в виду какая-то конкретнаясимметричная положительно определённая матрица A.ОпределениеДля заданной симетричной положительно определённойматрицы A норма k · kA называется энергетической нормойотносительно матрицы A.Нижний индекс указывает эту порождающую матрицу.Энергетическую норму k · kA часто называют также A-нормойвекторов, если в задаче имеется в виду какая-то конкретнаясимметричная положительно определённая матрица A.Термин «энергетическая» происходит из-за аналогии выражениядля этой нормы с выражениями для различных видов энергии вфизических системах.Симметричная матрица может быть приведена к диагональномувиду ортогональными преобразованиями подобия:A = Q⊤ D Q,где Q — ортогональная матрица, D = diag {λ1 , λ2 , .

. . , λn } —диагональная матрица, на главной диагонали которой стоятположительные собственнные значения λi матрицы A.ПоэтомуkxkA =p=pгде y = Qx.hAx, xi =qhQ⊤DQx, xihDQx, Qxi =phDy, yi =nXi=1λi yi2!1/2,(1)Поэтому в системе координат, которая получается ортогональнымпреобразованием x = Q⊤ y, поверхности уровня энергетическойнормы — kxkA = const, — являются эллипсоидами в Rn .Поэтому в системе координат, которая получается ортогональнымпреобразованием x = Q⊤ y, поверхности уровня энергетическойнормы — kxkA = const, — являются эллипсоидами в Rn .Эти эллипсоиды уровня тем более вытянуты, чем большеразличаются между собой собственные значения λi матрицы A,т.

е. чем больше её число обусловленности cond2 (A).x2x1Типичный шар единичного радиуса в энергетической нормеВ нормированном пространстве X шаром радиуса r с центром вточке a называется множество { x ∈ X | kx − ak ≤ r }.∞-норма2-норма❅❅❅❅❅1-нормаЕдиничным шаром, т. е. множеством { x | kxk ≤ 1 },даётся геометрически наглядное представление о норме.Из сказанного вытекает характерная особенность энергетическойнормы:энергетическя норма может существенно искажатьобычный геометрический масштаб объектов по разнымнаправлениям (своеобразная анизотропия).Из сказанного вытекает характерная особенность энергетическойнормы:энергетическя норма может существенно искажатьобычный геометрический масштаб объектов по разнымнаправлениям (своеобразная анизотропия).Это вызывается разбросом собственных значений порождающейматрицы A.В результате векторы из Rn ,имеющие одинаковую энергетическую норму,существенно различны по обычной евклидовой длине,и наоборот.Из общего факта эквивалентности любых норм в конечномерномлинейном пространстве следует, что энергетическая нормаэквивалентна рассмотренным выше векторным нормам k · k1 , k · k2 ,k · k∞ и k · kp .Из общего факта эквивалентности любых норм в конечномерномлинейном пространстве следует, что энергетическая нормаэквивалентна рассмотренным выше векторным нормам k · k1 , k · k2 ,k · k∞ и k · kp .Но интересно знать конкретные константы эквивалентности.Из выражения (1) следует, чтоmin λi kxk2 ≤ kxkA ≤ max λi kxk2 ,iiгде λi — собственные значения порождающей матрицы A.Из общего факта эквивалентности любых норм в конечномерномлинейном пространстве следует, что энергетическая нормаэквивалентна рассмотренным выше векторным нормам k · k1 , k · k2 ,k · k∞ и k · kp .Но интересно знать конкретные константы эквивалентности.Из выражения (1) следует, чтоmin λi kxk2 ≤ kxkA ≤ max λi kxk2 ,iiгде λi — собственные значения порождающей матрицы A.Для матричных норм, которые подчинены энергетической нормевекторов или просто согласованы с нею, даже не всегда можноуказать явный и несложно вычисляемый вид.Нестационарные итерационные методыдля решения систем линейных уравненийЕщё один факт, который служит теоретической основой длявариационных методов решения систем линейных алгебраическихуравнений:ТеоремаВектор x⋆ ∈ Rn является решением системы линейныхалгебраических уравнений Ax = b с симметричной положительноопределённой матрицей A тогда и только тогда, когда ондоставляет минимум функционалуΨ (x) = 21 hAx, xi − hb, xi.Доказательство.Если A — симметричная положительно-определённая матрица, то,как мы видели, выражением 12 hAx, xi задаётся так называемаяэнергетическая норма k · kA векторов из Rn .Доказательство.Если A — симметричная положительно-определённая матрица, то,как мы видели, выражением 12 hAx, xi задаётся так называемаяэнергетическая норма k · kA векторов из Rn .Далее, пусть x⋆ — решение рассматриваемой системы линейныхалгебраических уравнений Ax = b.

Оно существует и единственно всилу положительной определённости матрицы A.Доказательство.Если A — симметричная положительно-определённая матрица, то,как мы видели, выражением 12 hAx, xi задаётся так называемаяэнергетическая норма k · kA векторов из Rn .Далее, пусть x⋆ — решение рассматриваемой системы линейныхалгебраических уравнений Ax = b. Оно существует и единственно всилу положительной определённости матрицы A.Из единственности x⋆ следует, что некоторый вектор x ∈ Rnявляется решением системы уравнений тогда и только тогда,когда x − x⋆ = 0.Доказательство.Если A — симметричная положительно-определённая матрица, то,как мы видели, выражением 12 hAx, xi задаётся так называемаяэнергетическая норма k · kA векторов из Rn .Далее, пусть x⋆ — решение рассматриваемой системы линейныхалгебраических уравнений Ax = b.

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

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