∑П-разложения в задачах сжатия экспериментальных данных тема автореферата и диссертации по математике, 01.01.07 ВАК РФ

Введение.

1. Оценка эффективности ЕП-приближений случайных матриц. 11 1.1. Необходимые сведения из теории ЕП-аппроксимации и многомерного статистического анализа.

1.1.1. Алгоритм построения и основные свойства ЕП- аппроксимации в тензорном произведении гильбертовых пространств. .:.

1.1.2. Некоторые сведения из многомерного статистического анализа.•.

1.2. Анализ эффективности ЕП-приближений случайных матриц.1.

2. ЕП-приближения для двумерных задач на хаотических сетках.

2.1. Алгоритм построения ЕП-аппроксимации на двумерных хаотических сетках.

2.1.1. Основные сведения из теории сплайн-аппроксимации на двумерных хаотических сетках.

2.1.2. Алгоритм построения ЕП-приближений на двумерных хаотических сетках.

2.2. Статистический анализ эффективности ЕП-приближений на двумерных хаотических сетках. .

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

В известных работах А.Н. Колмогорова и его учеников [1 - 3] была решена проблема Представления функции многих переменных с помощью суперпозиций и сумм непрерывных функций меньшего числа переменных, а именно, была доказана следующая теорема. I

Теорема. При любом цЫом п > 2 существуют такие определенные на единичном отрезке Е1 = [0, 1] непрерывные действительные функции фр<1(х), что каждая определенная на n-мерном единичном кубе Еп непрерывная действительная функция f(x\,. . ., хп) пред-ставима в виде где функции Хд(у) действительны и непрерывны.

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

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

Проблема аппроксимации функций многих переменных суммами функций одного переменного рассматривалась в работах [4-6]. Однако такой способ приближения обладает одним весьма существенным недостатком. Дело в том, что величина погрешности п

Ef = mm\\f{xi,x2,.,xn) i=i вполне определяется функцией / и не может быть сделана меньше наперед заданной величины.

В этом смысле приближение функции нескольких переменных произведениями функций одного переменного обладает преимуществом, поскольку для остатка ri{xux2.хп) = f(xux 2,.,Я„) - ' ••• :<Pn4xn) можно вычислить следующее наилучшее приближение:

2(жЬ Ж2, • • • , хп) = ГХ(хи Х2, . . . , хп) - ^PlHxi)^ {xi) • ^пЧХп)

2)/

При этом (2) г2(х 1,х2,. .,ХП)\\ = min ||ri(a;i, дг2,. ,*arn) - П Ч>\ Лхг)\ уГ5 i=l ||/(яьЖ2,. - П - П ^!2)(жг)|| < г=1 г=1 ri(xi,x2,.,xn)\\. (0.1)

Таким образом, для достижения необходимой точности достаточно взять соответствующее число членов ряда П <р\%г) + П + . . ■ + П + • • • , (0-2) г=1 г—1 г=1 который строится последовательным повторением процедуры (0.1).

Впервые разложение в билинейный ряд (0.2) функции двух переменных в средне-квадратичной норме было сделано, по-видимому, в работе Шмидта уже в 1907 году [7]. Основные результаты этой работы достаточно подробно изложены в учебнике по математическому анализу Гурса [8].

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

Затем в шестидесятых годах в связи с развитием мощной цифровой вычислительной техники интерес к этому аппарату приближения функций многих перемейных возродился вновь [9, 10]. В работе [10] были повторены некоторые из результатов Шмидта и предложен метод для вычисления функций ряда. Кроме того, в ней содержатся примеры применения метода разложения в билинейный ряд для обработки изображений и фильтрации шумов.

Здесь следует отметить, что если в качестве функции двух переменных рассматривать прямоугольную матрицу, то приближение вида (0.2) есть ни что йное, как скелетное (сингулярное) разложение матрицы (подробнее Ь скелетных разложениях можно прочитать, например, в учебнике Гантмахера [11]). Поэтому в современной терминологии функции Шмидта ряда (0.2) обычно называют сингулярными функциями.

Дальнейшие исследования приближений функций двух переменных суммами произведений функций одного переменного были на» правлены на построение общей теории приближений в произвольном тензорном произведении ^гильбертовых пространств [12 - 15].

В работах [1214] был использован классический подход к построению ряда (0.2), берущий свое начало в уже упомянутой работе Шмидта. Разложение ви|ца (0.2) строится на всем тензорном произведении гильбертовых пространств.

В работе [15] Василенко предложил алгоритм построения разложения вида (0.2) (в современной терминологии ЕП-аппроксимации), где слагаемые ряда являются элементами конечномерного подпространства. Данное обстоятельство позволило существенно упростить вычислительные процедуры получения слагаемых разложения. Именно этот алгоритм (назовем его приближением на подпространстве) и взят за основу в предлагаемой диссертационной работе. Более подробно основы теории ЕП-аппроксимации рассмотрены в главе 1.

Оптимальная ЕП-аппроксимация достаточно успешно применялась в различных задачах численного анализа. В частности, одной из областей применения ЕП-разложений была аппроксимация функций на двумерных прямоугольных сетках. При этом использовалось два подхода. Первый заключался в построении ЕП-аппроксимации таблицы сеточной функции (представлении таблицы в виде суммы произведений одномерных векторов) с последующей одномерной сплайн-интерполяцией. Второй подход заключался в построении ЕП-приближения непосредственно двумерного сплайна на прямоугольной сетке. Достаточно успешное применение ЕП-аппроксимации для приближения функций, заданных в узлах прямоугольной двумерной сетки, послужило толчком для исследования возможности применения ее для аппроксимации функций, заданных в узлах хаотической сетки.

Практическое использование ЕП-приближений показало достаточную их эффективность. Однако до сих пор удовлетворительных аналитических или численных оценок эффективности получено не было. Рассмотрим величину

En(f) = inf ||f(x,y) - ± а^х)Ш\\ь2- (0-3) а.Д- i-i z

В работе Шмидта [7] доказано, что нижняя грань в правой части (0.3) достигается на фундаментальных функциях Шмидта, т.е. W i= 1 f^i где pi, фг - фундаментальные функции Шмидта, /лг- - сингулярные числа интегрального оператора с ядром f(x,y).

Известно [12, 13, 15], что вопрос о погрешности приближения функции отрезком билинейного ряда тесно связан с сингулярными чилами а именно 4>i(x)il>i(y)

2 ■■ -.а - 1

KU)= /(*,y)-Er,v т = ll/lli,-Elf2

1=1 Pi L2 {= 1 /ij

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

Автору данной работы не удалось получить аналитической оценки поведения сингулярных чисел в ряде (0.2). По-видимому, основной причиной сложности получения этих оценок является нелинейность отображения, сопоставляющего функции ее ЕП-ряд. Именно по этой причине вызвал интерес подход к анализу качества приближения с помощью билинейного ряда, предложенный в работе Поспелова [12]. Изложим кратко суть этого подхода.

Рассмотрим функции и конечного ранга п (т.е. билинейный ряд разложения вида (0.2) конечен). Каждой такой функции поставим в соответствие монотонную последовательность чисел п di = \{>--->dn = X1 Здесь Лj - коэффициенты разложения функции иу т.е. и ^ Н-----h Лп<рпфп.

При этом известно, что

J,9

Таким образом каждое множество Кп функций и, ||ii|| = 1 отображается в множество Qn векторов (tii,., dn), у которых п & = 1, > • • • > dn. г= 1 I

Обозначим это отображение символом Un. Определим на Кп оценочi ную функцию следующим образом:

НЩ С Кп) = v(Un(Ko)), где /л - мера Лебега н;а множестве нормированная так, что i{Qn) = 1. i

Пусть

Те,п = {иеКп\ Г (и) >£}. В работе было приведено доказательство слеудющей теоремы:

Теорема. Для всякого е > О р.(Те,п) —> 0, п -)• оо.

Фактически, теорему молено переформулировать следующим образом:

Теорема. Для всякого е > О вероятность того, что у случайно взятой из множества Кп функции ее остаток после приближения одним слагаемым билинейного ряда будет больше е, стремится к О при п —> оо.

Автором диссертационной работы была предпринята попытка адаптировать результаты теоремы к алгоритму приближения на подпространстве. Однако более тщательное изучение подхода выявило некоторые его недостатки.

Во-первых, в оценочных формулах никак не отражены свойства отображения, сопоставляющего функции набор коэффициентов ЕП-разложения. Тем самьш, нигде не использовалось свойство, что Ai,.,An являются сингулярными числами интегрального оператора.

Во-вторых, в предложенном методе оценки предполагается, что коэффициенты c?i,. .,dn имеют равномерное распределение. Как будет показано далее в главе 1, это утверждение в общем случае не верно.

Кроме того, в данной работе была допущена техническая ошибка при вычислении меры > исказившая: итоговый результат.

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

Первая глава диссертационной работы посвящена выводам формул для простой вычислительной процедуры, позволяющей получить численную оценку эффективности ЕП-приближений для класса матриц одинаковой размерности, имеющих нормальное распределение. При выводе формул использовались результаты из многомерного статистического анализа для случайных матриц. В дополнение приводятся результаты численных экспериментов для некоторых классов матриц.

Введение. 10

Во второй главе рассматривается проблема построения оптимальной ЕП-аппроксимации функций, заданных в узлах хаотической сетки. В первой части главы предлагается алгоритм построения ЕП-аппроксимации. Вторая часть посвящена методике получения оценок, у подобных оценкам из первой главы, для ЕП-приближений функций, заданных в узлах хаотической двумерной сетки. Описана схема вычислительного процесса получения численных оценок. Так же, как и в первой главе, приводятся результаты проведенных численных экспериментов.

Заключение. 43

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

1. Колмогоров А.Н. О представлении непрерывных функций нескольких переменных суперпозициями непрерывных функций меньшего числа переменных // ДАН СССР, 1956, Т. 108, С. 178-182.

2. Арнольд В.И. О функциях трех переменных // ДАН СССР, 1957, Т. 114, №4, С. 679-683.

3. Колмогоров А.Н. О представлении непрерывных функций нескольких переменных в виде суперпозиций непрерывных функций одного переменного и сложения // ДАН СССР, 1957, Т. 114, №5, С. 953-956.

4. Оффман Ю.П. О наилучшем приближении функций двух переменных функциями вида ср(х) + ф{у) // Изв. АН СССР, сер. матем., 1961. Т. 25. №2. С. 232-252.

5. Бабаев М.А. О точных оценках приближения функций многих переменных суммами функций меньшего числа переменных // Матем. заметки, 1972. Т. 12. №1. С. 105-114.

6. Хавинсон С.Я. Чебышевская теорема для приближения функции двух переменных суммами <р(х) + ф{у\ // Изв. АН СССР, сер. матем., 1969. Т. 33. №3. С. 650-666. j

7. Е. Schmidt Zur Theorie der Linearen und Nichtlinearen Integralgleichungen // Math.

8. Ann., 1907, Vol. 63, p. 433476.

9. Гурса Э. Курс математического анализа Т. 3, Часть 2: Онти, 1934.

10. Шура-Бура М.Р. Аппрокскмация функций многих переменных функциями, каждая из которых зависит от одного переменного // Сб. «Вычисл. матем.», 1957, №2. С. 3-19.

11. Баглай Р.Д., Смирнов К.К. К обработке двумерных сигналов на. ЭВМ // ЖВМ и МФ, 1975. Т. 15. №1. С. 241-248.f

12. Гантмахер Ф.Р Теория матриц Москва: Наука, 1967.

13. Поспелов В.В. О приближении функций нескольких переменных суммами произведениями функций одного переменного // Препринт №32. М.: ИПМ АН СССР. 1978.1. Литература45

14. Поспелов В.В. О погрешности приближения функций двух переменных суммами произведений функций одного переменного //ЖВМ и МФ, 1978. Т. 18. №5. С. 1307-1308.14