Система линейных алгебраических уравнений с интервальными коэффициентами. Рассмотрим систему линейных алгебраических уравнений вида

, (9.39)

где S Î I (R^{p ´ n}), F Î I (Rⁿ). Уравнение (9.39) понимается в следующем смысле: требуется найти множество

.

Обозначим . Множество решений может иметь весьма замысловатую структуру. Например, Хансен показал, что при

(9.40)

изображается на плоскости (u ₁, u ₂) в виде невыпуклого восьмиугольника.

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

В рамках интервального исчисления можно поставить задачу нахождения интервального вектора U = (U ₁, U ₂,..., U_n) такого, что , i = . Оптимальным интервальным решением назовем такой интервальный вектор U ^*, компоненты которого удовлетворяют условиям

где inf и sup берутся по всем возможным решениям:

. (9.41)

Для отыскания интервалов U_i, i = , применяют как прямые, так и итерационные методы. Прямые интервальные методы часто представляют собой непосредственное перенесение на интервальный случай обычных (вещественных) прямых методов.

9.1.8. Обращение интервальных матриц. Одним из способов решения системы уравнений (9.39) является использование обратной матрицы. Очевидно, что если нам известна матрица Т такая, что

, (9.42)

то множество решений системы содержится в TF: .

Первый интервальный метод нахождения такой матрицы был предложен Хансеном. Интервальная арифметика в нем используется в комбинации с априорными оценками некоторых величин.

Выберем матрицу s * Î S (например, s * = m (S)) и вычислим каким-либо способом матрицу t – приближение к *^-1. Определим P равенством P = e – St, где e – единичная матрица. Предположим, что || P || < 1. Тогда для любой вещественной матрицы p Î P справедливо следующее представление:

(e – p)^-1 = e + p + p ² + …. (9.43)

Обозначив r_m = t + p + p ² + … + p^m, получим неравенство

. (9.44)

Если s Î S, то t – st = p Î P и, значит, (e – p)^-1 = (st)^-1 = t ^-1 s ^-1, откуда

s ^-1 = t (e – p)^-1. (9.45)

Пусть – матрица, все элементы которой равны [-e _m, e _m ]^-1.

Из (9.45) имеем s ^-1 Î t (r_m + E_m).

Определим интервальную матрицу R_m соотношением

R_m = (... ((P + e) P + e) P +..) + e (m сложений).

Тогда s ^-1 Î t (r_m + E_m) для любой матрицы s Î S.

Пусть теперь s Î R^{n ´ n} – невырожденная вещественная матрица, а матрица T ⁽⁰⁾ Î I(R^{n ´ n}) такова, что s ^-1 Î T ⁽⁰⁾.

9.1.9. Интервальные итерационные методы для систем линейных алгебраических уравнений. Применение интервальных методов гарантирует не только быструю сходимость решения за счет обеспечения последовательного включения решений без особых затрат памяти ЭВМ, но и возможность проверки существования и единственности решения нелинейных систем в заданной области пространства Rⁿ и сходимости соответствующих итерационных процессов. Обычные вещественные итерационные методы типа метода Ньютона гарантированно сходятся к решению лишь тогда, когда начальное приближение выбрано достаточно близко к нему.

Пусть система линейных алгебраических уравнений записана в виде

x = ax + b; (9.46)

(9.47)

причем относительно а и b известно, что a Î A, b Î B.

В качестве примера интервальных итерационных методов для (9.45) рассмотрим метод простой итерации.

Теорема 9.2. Итерации

, (9.48)

cходятся к единственной неподвижной точке уравнения

X = A X + B

при любом начальном Х ⁽⁰⁾ Î I (Rⁿ) тогда и только тогда, когда r (| A |) < 1.

Еще один подход к построению итерационных методов для системы (9.39) состоит в следующем. Умножим обе части этого уравнения на невырожденную матрицу Y, например, Y» (m (S))^-1 и положим T = e – Ys. Если || T || < 1, то возьмем вектор такой U ⁽⁰⁾ Î I (Rⁿ), что Ì U ⁽⁰⁾, и определим последовательность

. (9.49)

Справедлива следующая теорема.

Теорема 9.3. Если для некоторой матрицы Y справедливо неравенство

|| e – Ys || £ 1,

то, каковы бы ни были s Î S, f Î F, система имеет единственное решение и при любом k ³ 0 это решение содержится в интервальном векторе U (k), найденном с помощью (9.49).

В качестве U (0) можно взять, например, вектор с компонентами

.

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

Ax = b, (9.50)

где A Î M_nn (I) R)), b Î V_n (I) R)), M_nn (I) R)), V_n (I) R)), I (R) – множества интервальных nn -матриц, n -векторов и чисел соответственно.

В интервальном анализе ищут обычно так называемое поточечное решение системы интервальных уравнений (9.50), т. е. множество

x ^* = {| x | Ax = b, A Î A, b Î b }. (9.51)

Такое понятие поточечного решения не удовлетворяет сложившейся концепции решения уравнения, т. е. подстановка найденного x * в (9.73) не дает равенства левой и правой частей уравнений.

Существуют также стандартные пакеты прикладных программ по решению систем уравнений с интервальными матрицами коэффициентов. Для линейной системы уравнений Ax = b существует интервальный аналог метода Ньютона - Гаусса - Зейделя. Этот метод требует незначительных затрат по памяти и времени на каждом шаге, но может медленно сходиться.

Современные методы интервального анализа, кроме основных арифметических операций над интервальными величинами, содержат развитые средства для решения систем линейных и нелинейных уравнений, методы решения дифференциальных уравнений и т. д.

Целью интервального анализа при решении дифференциальных уравнений является получение строгих верхних и нижних границ решения по заданным границам (интервалам) исходных данных (начальных и граничных значений, коэффициентов уравнений и т. п.). Эти методы применимы для решения линейных и нелинейных обыкновенных дифференциальных уравнений в частных производных и являются более надежными, строгими и простыми по сравнению с классическими методами решения дифференциальных уравнений. Кроме того, в них автоматически учитывается неточность, связанная с ошибками округления ЭВМ.

Использование понятия интервальных ограничений и кода Hensel дало возможность создать специальные методы для ЭВМ, свободные от ошибок округления, и применить их для решения целого ряда приложений (решение систем линейных уравнений, интервального линейного программирования и т. д.).