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

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

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

. . , min{m, n} — квадратысингулярных чисел σi матрицы A, и, возможно,ещё нули в случае m < n.ДалееkAxk2= maxkAk2 = maxx6=0x6=0 kxk2√√x∗A∗A xx∗ U ∗ΛU x√√=maxx6=0x∗ xx∗ U ∗ U xsP√22(U x)∗Λ(U x)z ∗Λ zi σi |zi |P= max p= max √ ∗= max2x6=0z6=0z6=0z z(U x)∗ U xi |zi |p≤ max σmax (A)z6=0sP|z |2Pi i 2i |zi |!= σmax (A),где в выкладках применена замена переменных z = U x.ДалееkAxk2= maxkAk2 = maxx6=0x6=0 kxk2√√x∗A∗A xx∗ U ∗ΛU x√√=maxx6=0x∗ xx∗ U ∗ U xsP√22(U x)∗Λ(U x)z ∗Λ zi σi |zi |P= max p= max √ ∗= max2x6=0z6=0z6=0z z(U x)∗ U xi |zi |p≤ max σmax (A)z6=0sP|z |2Pi i 2i |zi |!= σmax (A),где в выкладках применена замена переменных z = U x.Кроме того, полученная для kAk2 оценка достижима: достаточновзять в качестве вектора z столбец единичной n × n-матрицы2 (A) на диагонали в Λ,с номером, равным месту элемента σmaxа в самом начале выкладок положить x = U ∗ z.Вычислительные методыанализа и линейной алгебрыКурс лекцийС.П.

ШарыйКафедра математического моделирования НГУЛекция 24 ноября 2017 г.Спектральный радиусОпределениеСпектральным радиусом квадратной матрицы называетсянаибольший из модулей её собственных чисел.Imρ0ρ(A) = max |λ(A)|ReСпектральный радиусЭквивалентное определение: спектральным радиусом матрицыназывается наименьший из радиусов кругов комплексной плоскостиC с центрами в нуле, которые содержат весь спектр матрицы.Imρ0ρ(A) = max |λ(A)|ReПредложениеСпектральный радиус матрицы не превосходит любой её нормы.ПредложениеСпектральный радиус матрицы не превосходит любой её нормы.Набросок доказательства: Пусть λ — собственное значениематрицы A, пусть v 6= 0 — соответствующий собственный вектор,так чтоAv = λv.ПредложениеСпектральный радиус матрицы не превосходит любой её нормы.Набросок доказательства: Пусть λ — собственное значениематрицы A, пусть v 6= 0 — соответствующий собственный вектор,так чтоAv = λv.Возьмём от обеих частей этого равенства норму, которой подчиненарассматриваемая норма матрицы kAk.

ПолучимkAk · kvk ≥ kAvk = kλvk = |λ| · kvk,где kvk > 0, и потому сокращение на эту величину обеих частейнеравенства даёт kAk ≥ |λ|.ПредложениеСпектральный радиус матрицы не превосходит любой её нормы.Набросок доказательства: Пусть λ — собственное значениематрицы A, пусть v 6= 0 — соответствующий собственный вектор,так чтоAv = λv.Возьмём от обеих частей этого равенства норму, которой подчиненарассматриваемая норма матрицы kAk.

ПолучимkAk · kvk ≥ kAvk = kλvk = |λ| · kvk,где kvk > 0, и потому сокращение на эту величину обеих частейнеравенства даёт kAk ≥ |λ|.Так как наше рассуждение справедливо для любого собственногозначения λ, то в самом деле max |λ| = ρ(A) ≤ kAk.В общем случае это рассуждение может быть некорректным,если у вещественной матрицы A собственные значения исобственные векторы будут комплексными.Тем не менее, идея доказательства верна и его можноскорректировать, выполнив комплексификацию пространства.Опускаем эти построения из-за недостатка времени.В общем случае это рассуждение может быть некорректным,если у вещественной матрицы A собственные значения исобственные векторы будут комплексными.Тем не менее, идея доказательства верна и его можноскорректировать, выполнив комплексификацию пространства.Опускаем эти построения из-за недостатка времени.Спектральные радиус не является нормой, так как для него невыполнена даже первая аксиома нормы: для ненулевой матрицы0 101..

.... 0 1000— жордановой клетки, отвечающей собственному значению 0,спектральный радиус равен нулю.Спектральный радиусСпектральный радиус является важной характеристикой матрицы,которая описывает асимптотическое поведение её степеней.ТеоремаПусть A — квадратная матрица, вещественная или комплексная.Для того, чтобыlim Ak = 0,k→∞т. е. чтобы степени матрицы A сходились к нулевой матрице,необходимо и достаточно, чтобы ρ(A) < 1 — спектральный радиусматрицы A был меньше 1.Спектральный радиусСпектральный радиус является важной характеристикой матрицы,которая описывает асимптотическое поведение её степеней.ТеоремаПусть A — квадратная матрица, вещественная или комплексная.Для того, чтобыlim Ak = 0,k→∞т.

е. чтобы степени матрицы A сходились к нулевой матрице,необходимо и достаточно, чтобы ρ(A) < 1 — спектральный радиусматрицы A был меньше 1.Доказательство достаточности опускается.Доказательство необходимости.Пусть λ — собственное число матрицы A, v 6= 0 — его собственныйвектор. Тогда Av = λv, и потомуA2 v = A(Av) = A(λv) = λ(Av) = λ2 v,A3 v = A(A2 v) = A(λ2 v) = λ2 (Av) = λ3 v,......,так что в целомAk v = (λk )v.Доказательство необходимости.Пусть λ — собственное число матрицы A, v 6= 0 — его собственныйвектор.

Тогда Av = λv, и потомуA2 v = A(Av) = A(λv) = λ(Av) = λ2 v,A3 v = A(A2 v) = A(λ2 v) = λ2 (Av) = λ3 v,......,так что в целомAk v = (λk )v.Если последовательность степеней Ak , k = 0, 1, 2, . . . , сходится кнулевой матрице, то при фиксированном векторе v нулевой пределимеет также левая часть равенства.Доказательство необходимости.Пусть λ — собственное число матрицы A, v 6= 0 — его собственныйвектор. Тогда Av = λv, и потомуA2 v = A(Av) = A(λv) = λ(Av) = λ2 v,A3 v = A(A2 v) = A(λ2 v) = λ2 (Av) = λ3 v,......,так что в целомAk v = (λk )v.Если последовательность степеней Ak , k = 0, 1, 2, . . . , сходится кнулевой матрице, то при фиксированном векторе v нулевой пределимеет также левая часть равенства.Поэтому к нулевому вектору должна сходиться и правая часть,причём v 6= 0.

Это возможно лишь в случае |λ| < 1.Число обусловленности матрицРассмотрим систему линейных алгебраических уравненийAx = bс неособенной квадратной матрицей A, det A 6= 0, и векторомправой части b 6= 0.Число обусловленности матрицРассмотрим систему линейных алгебраических уравненийAx = bс неособенной квадратной матрицей A, det A 6= 0, и векторомправой части b 6= 0.Пусть(A + ∆A) x̃ = b + ∆b— возмущённая система уравнений, где ∆A ∈ Rn×n и ∆b ∈ Rn —возмущения матрицы и вектора правой части.Число обусловленности матрицРассмотрим систему линейных алгебраических уравненийAx = bс неособенной квадратной матрицей A, det A 6= 0, и векторомправой части b 6= 0.Пусть(A + ∆A) x̃ = b + ∆b— возмущённая система уравнений, где ∆A ∈ Rn×n и ∆b ∈ Rn —возмущения матрицы и вектора правой части.Вопрос:Насколько сильно ненулевое решение x̃ возмущённой системыможет отличаться от решения x исходной системы уравнений?Пусть ∆x = x̃ − x, так что x̃ = x + ∆x, и потому(A + ∆A)(x + ∆x) = b + ∆b.Пусть ∆x = x̃ − x, так что x̃ = x + ∆x, и потому(A + ∆A)(x + ∆x) = b + ∆b.Вычитая из этого равенства исходную систему уравнений Ax = b,получим(∆A) x + (A + ∆A) ∆x = ∆b,или(∆A)(x + ∆x) + A ∆x = ∆b.Пусть ∆x = x̃ − x, так что x̃ = x + ∆x, и потому(A + ∆A)(x + ∆x) = b + ∆b.Вычитая из этого равенства исходную систему уравнений Ax = b,получим(∆A) x + (A + ∆A) ∆x = ∆b,или(∆A)(x + ∆x) + A ∆x = ∆b.Вспоминая, что x + ∆x = x̃, можно заключить∆x = A−1 −(∆A) x̃ + ∆b .Для оценки величины изменения решения ∆x воспользуемсякакой-нибудь удобной нам векторной нормой.Применяя её к обеим частям выражения для ∆x, будем иметьk∆xk ≤ kA−1 k · k∆Ak kx̃k + k∆bkпри согласовании используемых векторных и матричных норм.Для оценки величины изменения решения ∆x воспользуемсякакой-нибудь удобной нам векторной нормой.Применяя её к обеим частям выражения для ∆x, будем иметьk∆xk ≤ kA−1 k · k∆Ak kx̃k + k∆bkпри согласовании используемых векторных и матричных норм.Предполагая, что возмущённое решение x̃ не равно нулю, можемподелить обе части на kx̃k > 0, придя к неравенствуk∆bkk∆xk−1≤ kA k · k∆Ak +kx̃kkx̃k−1= kAk kAk ·k∆Akk∆bk+kAkkAk · kx̃k.(1)Получена апостериорная оценка относительной погрешностирешения, которую удобно применять после того, как приближённоерешение системы уже найдено.Получена апостериорная оценка относительной погрешностирешения, которую удобно применять после того, как приближённоерешение системы уже найдено.Так какkAk · kx̃k ≥ kAx̃k ≈ kbk,то знаменатель второго слагаемого в скобках из правой частинеравенства «приблизительно не меньше» kbk.Получена апостериорная оценка относительной погрешностирешения, которую удобно применять после того, как приближённоерешение системы уже найдено.Так какkAk · kx̃k ≥ kAx̃k ≈ kbk,то знаменатель второго слагаемого в скобках из правой частинеравенства «приблизительно не меньше» kbk.Поэтому оценке (1) путём некоторого огрубления можно придатьболее элегантный видk∆Ak k∆bkk∆xk−1/ kA k kAk ·+,(2)kx̃kkAkkbkв котором справа задействованы относительные погрешности вматрице A и правой части b.Число обусловленности матрицФигурирующая в оценках (1) и (2) величина kA−1 k kAk, на которуюсуммарно умножаются ошибки в матрице и правой части играетважнейшую роль в вычислительной линейной алгебре.Число обусловленности матрицФигурирующая в оценках (1) и (2) величина kA−1 k kAk, на которуюсуммарно умножаются ошибки в матрице и правой части играетважнейшую роль в вычислительной линейной алгебре.ОпределениеДля квадратной неособенной матрицы A величина kA−1 k kAkназывается её числом обусловленности (относительно выбраннойнормы матриц).Число обусловленности матрицФигурирующая в оценках (1) и (2) величина kA−1 k kAk, на которуюсуммарно умножаются ошибки в матрице и правой части играетважнейшую роль в вычислительной линейной алгебре.ОпределениеДля квадратной неособенной матрицы A величина kA−1 k kAkназывается её числом обусловленности (относительно выбраннойнормы матриц).Число обусловленности матрицы A обозначают cond(A),иногда с индексом, указывающим выбор нормы.Число обусловленности матрицФигурирующая в оценках (1) и (2) величина kA−1 k kAk, на которуюсуммарно умножаются ошибки в матрице и правой части играетважнейшую роль в вычислительной линейной алгебре.ОпределениеДля квадратной неособенной матрицы A величина kA−1 k kAkназывается её числом обусловленности (относительно выбраннойнормы матриц).Число обусловленности матрицы A обозначают cond(A),иногда с индексом, указывающим выбор нормы.Если det A = 0, то удобно положить cond(A) = +∞.Иллюстрация возмущения решения 2 × 2-системы линейныхуравнений с хорошей обусловленностью матрицы— малые «шевеления» прямых приводятк малым изменениям в решении.Иллюстрация возмущения решения 2 × 2-системы линейныхуравнений с плохой обусловленностью матрицы— малые «шевеления» любой прямой приводятк большим изменениям в решении.Число обусловленности матрицАприорная оценка относительной погрешности численного решениясистемы линейных алгебраических уравнений через оценкиотносительных погрешностей её матрицы и правой части:k∆xk≤kxkcond(A)·k∆Ak1 − cond(A) ·kAkk∆Ak k∆bk+,kAkkbkЧисло обусловленности матрицАприорная оценка относительной погрешности численного решениясистемы линейных алгебраических уравнений через оценкиотносительных погрешностей её матрицы и правой части:k∆xk≤kxkcond(A)·k∆Ak1 − cond(A) ·kAkДоказательство опускается.k∆Ak k∆bk+,kAkkbkЧисло обусловленности матрицКак находить или хотя бы оцениватьчисла обусловленности матриц?Число обусловленности матрицКак находить или хотя бы оцениватьчисла обусловленности матриц?Для спектральной матричной нормы k · k2 , подчинённой евклидовойнорме векторов, число обусловленности матрицы имеет элегантноеявное выражение.Число обусловленности матрицКак находить или хотя бы оцениватьчисла обусловленности матриц?Для спектральной матричной нормы k · k2 , подчинённой евклидовойнорме векторов, число обусловленности матрицы имеет элегантноеявное выражение.Вспомогательный результатПредложениеЕсли σ — сингулярное число неособенной квадратной матрицы A,то σ −1 — это сингулярное число обратной к ней матрицы A−1 .Доказательство:Напомним, что собственные числа взаимно обратных матрицобратны друг другу: если C — неособенная n × n-матрица иCv = λv, то v = λC −1 v, и, так как λ 6= 0 в силу det C 6= 0,получаем отсюда C −1 v = λ−1 v.Доказательство:Напомним, что собственные числа взаимно обратных матрицобратны друг другу: если C — неособенная n × n-матрица иCv = λv, то v = λC −1 v, и, так как λ 6= 0 в силу det C 6= 0,получаем отсюда C −1 v = λ−1 v.Применим этот факт к матрице A∗A.

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

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