Вернутся на главную

Обусловленность решения


Обусловленность решения на нашем сайте

Статьи
Статьи для студентов
Статьи для учеников
Научные статьи
Образовательные статьи Статьи для учителей
Домашние задания
Домашние задания для школьников
Домашние задания с решениями Задания с решениями
Задания для студентов
Методички
Методические пособия
Методички для студентов
Методички для преподавателей
Новые учебные работы
Учебные работы
Доклады
Студенческие доклады
Научные доклады
Школьные доклады
Рефераты
Рефератывные работы
Школьные рефераты
Доклады учителей
Учебные документы
Разные образовательные материалы Разные научные материалы
Разные познавательные материалы
Шпаргалки
Шпаргалки для студентов
Шпаргалки для учеников
Другое

Простейшей моделью принятия решений в матричном представлении является задача решения системы линейных алгебраических уравнений, которая записывается выражением

Ax = b, (1)

где: А = {aij}, i, j = 1…n - матрица коэффициентов уравнения;

b– вектор свободных членов;

x – вектор решения.

В данном случае не принципиально даже то, что для модели сознания такая модель принятия решений представляется не совсем очевидной: в любом случае анализ такой постановки имеет универсальное значение. Позиция математики при решении любой задачи состоит в том, что подлежат безусловному рассмотрению, по меньшей мере, следующие вопросы:

§ существование решения:

§ его единственность;

§ качество решения.

Вопросы существования и единственности решения системы (1) априори предполагаются решёнными положительно, т.е. det(A) ≠ 0, существует единственная обратная матрица А-1 и решение представлено в виде x = A-1*b, а исследуется только его устойчивость. По сути, в этой главе приводятся полные доказательства тех результатов по обусловленности решения, которые в предыдущей главе упомянуты без доказательства. Пусть исходные данные этой системы заданы с погрешностями соответственно ΔА и Δb, что вызовет погрешность решения Δx. Тем самым исходная система (1) трансформируется к виду

(A + ΔА) * (x + Δx) = b + Δb (2)

Оценим погрешность Δx и её соотношение с точным решением. Для этого придётся перейти к специальным скалярным величинам. Как векторам, так и матрицам, удобно сопоставить некоторые одномерные числовые значения – нормы, в определённом смысле характеризующие величину исходных объектов. Понятие нормы вектора вводится аксиоматически следующими свойствами:

1. ║x║ > 0 при x ≠ 0 и ║0║ = 0, где ║.║- знак некоторой векторной нормы;

2. ║k * x║ = │k│ * ║x║ для любого действительного k;

3. ║x + y║ <= ║x║ + ║y║ - неравенство треугольника.

Свойствам 1 – 3 удовлетворяет используемая далее евклидова норма вектора, определяемая формулой

║x║ = 2

Матричная норма вводится аналогичными 1 - 3 свойствами с добавлением свойства Коши - Буняковского

4. ║A * C║ <= ║A║ * ║C║.

Свойствам 1 – 4 удовлетворяет матричная норма, подчинённая евклидовой векторной норме, и определяемая выражением

║A║ = max ║Ax║

║x║= 1

Для нахождения оценки Δx вычтем (1) из (2) и получим:

(A + ΔA) * Δx = Δb – ΔA * x (3)

Чтобы разрешить (3) относительно Δx, необходимо выяснить условие существования обратной матрицы (A + ΔA)-1. Представим (A + ΔA) в виде A + ΔA = A(E + A-1 * ΔA). Как вспомогательный результат получим условие существования обратной матрицы (E + C)-1. Известно, что если матрица (E + C)-1 существует, то правомерно её разложение в степенной матричный ряд Неймана:

(E + C)-1 = E + C + C2 + C3 + … (4)

Ряд (4) всегда сходится, когда сходится соответствующий числовой ряд

1 + ║C║ + ║C║2 + ║C║3 + … (5)

Ряд (5) сходится при условии ║C║ < 1, что и является достаточным условием существования матрицы (E + C)-1. Итак, матрица (A + ΔA)-1 существует, если

║A-1 * ΔA║ < 1 (6)

В предположении (6) абсолютная оценка погрешности решения имеет вид

Δx = (E + A-1 * ΔA)-1 * A-1 * (Δb – ΔA * x) (7)

Для перехода к числовой оценке необходимо оценить ║(E + A-1 * ΔA)-1║. Применив к (4) неравенства Коши – Буняковского и треугольника, получим

║(E + C)-1║ <= ║E║ + ║C║ + ║C║2 + ║C║3 + … (8)

Так как в правой части (8) при ║C║ < 1 записана сумма бесконечной убывающей геометрической прогрессии, то ║(E + C)-1║ <= 1 / (1 - ║C║). Отсюда

║Δx║ <= ║(E + A-1 * ΔA)-1║ * ║A-1║ * (║Δb║ – ║ΔA * x║) <=

║A-1║ * (║Δb║ – ║ΔA * x║) / (1 - ║A-1 * ΔA║)(9)

Более информативной, чем абсолютная оценка (9), является относительная оценка погрешности решения. Так как ║b║ <= ║A ║ * ║x║, то в предположении b ≠ 0

1 / ║x║ <= ║A ║ / ║b║ (10)

Умножая (9) на (10), получим верхнюю оценку для относительной погрешности решения

║Δx║ / ║x║ <= (║A║ * ║A-1║) / (1 - ║A-1 * ΔA║) * (║Δb║ / ║b║ - ║ΔA║ / ║A║) (11)

Другим способом аналогичный результат получен в [1]. Отметим, что всегда можно построить пример, в котором указанная оценка достигается, т.е. неравенство (11) не улучшаемо.

Аналогичным образом можно исследовать частные случаи и показать, что:

1. Если матрица задана точно, а вектор с погрешностью, то

║Δx║ / ║x║ <= (║A║ * ║A-1║) * (║Δb║ / ║b║);

2. Если матрица задана с погрешностью, а вектор известен точно, то

║Δx║ / ║x║ <= (║A║ * ║A-1║) / (1 - ║A-1 * ΔA║) * (║ΔA║ / ║A║).

Во всех трёх случаях фигурирует множитель ║A║ * ║A-1║. Это число является одной из принятых характеристик обусловленности матрицы и обозначается cond A [2] (H – число обусловленности [3], спектральное число обусловленности [4]). Для оценки cond A применим неравенство Коши - Буняковского к тождеству A * A-1 ≡ E:

cond A = ║A║ * ║A-1║ >= ║E║ = 1

Если А – симметричная матрица, то возможна точнаяоценка cond A [2 - 4]:

сond A = ║A║ * ║A-1║ = μmax / μmin , (12)

где μmax , μmin – соответственно максимальное и минимальное по модулю характеристические значения (собственные числа) матрицы А. Многие фундаментальные свойства матрицы А зависят от того, как она обеспечивает кратные преобразования некоторых векторов x,т.е. Ax = μx. Значения коэффициентов кратности μпри этомпреобразовании называютсясобственными числами матрицы А. Представляет значительный интерес голографическая интерпретация собственных чисел. Голография – это такой физический процесс, при котором запись одной и той же информации повторяется в любом масштабе и в любой точке записывающего пространства. Если матрицу А трактовать в смысле универсального голографического преобразования, то её собственные значения по определению естественно интерпретировать как масштабные множители.

Для прямоугольных матриц общего вида оценка (12) может быть представлена в аналогичном виде:

сond A = ║A║ * ║A-1║ = sup (h(Ax) / h(x)) / inf (h(Ax) / h(x)),

h(x) ≠ 0 h(x) ≠ 0

где sup, inf– наибольшая и наименьшая верхняя грань некоторой векторной нормы h(Ax).Матрица А и решение x системы (1) называются плохо обусловленными, если значение сond A достаточно велико. Получим выражение для нижней границы оценки относительной погрешности решения. Очевидно, что со стороны обусловленности нижняя граница оценки ║Δx║ / ║x║ определяется минимальным значением сond A, т.е.

║Δx║ / ║x║ >= 1 / (1 - ║A-1 * ΔA║) * (║Δb║ / ║b║ - ║ΔA║ / ║A║) (13)

Неравенства (11) и (13) разрешают следующий вывод: В общем случае относительная погрешность решения системы (1) превышает суммарную величину относительных погрешностей задания исходной информации, а величина этого превышения в значительной степени определяется обусловленностью матрицы А. С некоторой натяжкой этот вывод может быть интерпретирован в терминах доверительных интервалов: решение системы (1) будет тем достовернее, чем меньше значение сond A.

В евклидовом пространстве существует класс ортогональных матриц {U} – таких, что U * UT = UT * U = E,где UT – транспонированная к Uматрица, а cond U = 1 [2, 4]. Решение системы (1) будет тем меньше восприимчиво к действию погрешностей в исходной информации, чем больше матрица А близка к ортогональной матрице. Увы, процесс ортогонализации Грама – Шмидта для этих целей не подходит, так как ортонормированный базис зависит от порядка фиксации ортогонализуемых векторов. Поэтому Дж. Х. Уилкинсон предложил выход, состоящий в таком масштабировании исходной информации, при котором исходная матрица определённым образом уравновешивается. Матрица называется уравновешенной, если длины её строк и столбцов (в евклидовой норме) совпадают и равны единице. Практические алгоритмы уравновешивания и вопросы их сходимости рассматриваются в работе В. В. Шакина [5].






Название статьи Обусловленность решения