Рассмотрим трёхдиагональную матрицу

А

(

V

0\ О

о

-1

2/

a.Найдите LU-разложение матрицы А.

b.Используя прямую и обратную подстановку, решите систему Ах=(1 1 1 1 1)Т.

c.Найдите обратную матрицу А-1.

d.Покажите, как решать систему Ах = Ь с положительно определённой симметрической трёхдиагональной (га X га)-матрицей А за время О (га), используя LU-разложение. Объясните, почему любой алгоритм, основанный на обращении матрицы А, имеет асимптотически худшую оценку сложности.

e.Покажите, как решать систему Ах = Ь с невырожденной трёхдиагональной (га X га)-матрицей А за время О (га), используя LUP-разложение.

31-3 Сплайны

Проводя кривые через заданные точки, часто используют кубические сплайны (cubic splines). Пусть задан набор (га + 1) точек {(xi,yi) : г = 0,1,..., га}, причём жо < х\ < • • • < хп. Мы хотим провести через все эти точки кривую, состоящую из кусков га кубических полиномов, на каждом отрезке свой. Когда ж пробегает отрезок [xi, Xi+i] [г = 0,1,..., га), сплайн / определяется равенством /(ж) = /г(ж - жг), где /г(ж) = щ + 6гж + сгж2 + d{X3 - кубический полином. Точки жг-, в которых куски состыковываются, называются узлами (knots) Для простоты будем предполагать, что Xi = г при г = 0,1,... , га.

Потребовав от / непрерывности, получим условия:

f(Xi)

МО)

Mi)

Уг, У г +

для г = 0,1,... , га - 1. Отсутствие изломов (разрывов первой производной) в узлах даёт условия

/(жг+1) = Л(1) = Л+1(о),

для г = 0,1,

, га - 1.

а. Пусть мы каким-то образом выбрали, помимо самих значений yi = f(xi), ещё и производные Di = /(жг) в каждом узле. Выразите коэффициенты аг-, bi, Ci и d8- через значения уг-,Di и -D8+i- (На-

поминаем, что Xi = г.) Сколько времени понадобится для такого вычисления?

Если значения производной в узлах не заданы, встаёт вопрос об их выборе. Один из методов состоит в том, чтобы потребовать непрерывности вплость до второй производной /". Это даёт набор условий:

Г(Жг+1) = Л(1) = Л+1(о),

для г = 0,1,... , п - 1. Пока что значения второй производной / в точках жо и хп никак не ограничиваются; положив f"(xo) = /о(0) = О и f"(xn) = f"(l) = 0, получаем так называемый естественный кубический сплайн (natural cubic spline).

b.Используя непрерывность вплоть до второй производной, покажите, что

Д- 1 + 4Д- + Д+1 = 3(y,-+i - уг-г)(31.35)

для г = 1,... ,п - 1.

c.Для естественных кубических сплайнов докажите равенства

2Д + 4£)1 = 3(у1-у0),(31-36)

Dn i + 2Dn = Цуп - yn i).(31.37)

d.Перепишите уравнения (31.35)-(31.37) в виде матричного уравнения на вектор неизвестных D = (Dq,D\,... ,Dn). Какими свойствами обладает матрица этого уравнения?

e.Докажите, что естественный кубический сплайн для п + 1 точек можно построить за время 0(п) (ср. задачу 31-2).

f.Как построить естественный кубический сплайн для п + 1 точек (жо, уо), (хп, уп), у которых жо < х\ < • • • < хп, (но не обязательно Х{ = г). Какое матричное уравнение придётся решать и сколько времени для этого потребуется?

Замечания

Теория численных методов - целая наука, которой мы едва коснулись. Мы особенно рекомендуем следующие учебники: Джордж и Лью [18], Голуб и ван Лоан [89], Пресс, Флэнери, Тьюкольски и Веттерлинг [161,162], Стренг [181,182].

Появление работы Штрассена [183] в 1969 году было большим сюрпризом - никто не ожидал, что обычный алгоритм умножения матриц не оптимален. С тех пор асимптотическая верхняя оценка сложности умножения матриц многократно улучшалась и достигла О (га2,376) (Копперсмит и Виноград [52]). Наглядное представление алгоритма Штрассена картинками с плюсами и минусами было использовано в работе Патерсона [15]. Фишер и Мейер [67] применили алгоритм Штрассена для умножения булевых матриц (теорема 31.10 этого раздела)

Метод Гаусса исключения неизвестных, применяющийся при построении LU- и LUP-разложения, был первым систематическим

методом решения систем линейных уравнений (и одним из первых численных алгоритмов). Его изобретение обычно связывают с именем К.Ф. Гаусса (1777-1855), хотя он был известен и раньше.

Алгоритм обращения за время время 0(ralg7) содержится в классической работе Штрассена [183]. Виноград [203] заметил, что В своей уже упоминавшейся работе [183] что умножение матриц не сложнее обращения; обратную оценку получили Ахо, Хопкрофт и Ульман [4].

Прекрасное изложение теории положительно определённых симметрических матриц (и вообще линейной алгебры) имеется в книге Стренга [182]. На с. 334 её автор пишет: «Меня часто спрашивают, бывают ли несимметричные положительно определённых матрицах. Я никогда не использую этого термина.»