Содержание к диссертации
Введение
1. Оценка эффективности ЕП-приближений случайных матриц . 11
1.1. Необходимые сведения из теории ЕП-аппроксимации и многомерного статистического анализа 11
1.1.1. Алгоритм построения и основные свойства ЕП- аппроксимации в тензорном произведении гильберто вых пространств 11
1.1.2. Некоторые сведения из многомерного статистического анализа 15
1.2. Анализ эффективности ЕП-приближений случайных матриц 17
2. ЕП-приближения для двумерных задач на хаотических сетках . 24
2.1. Алгоритм построения ЕП-аппроксимации на двумерных хаотических сетках 24
2.1.1. Основные сведения из теории сплайн-аппроксимации на двумерных хаотических сетках 24
2.1.2. Алгоритм построения ЕП-приближений на двумерных хаотических сетках 26
2.2. Статистический анализ эффективности ЕП-приближений на двумерных хаотических сетках. 30
Приложение
- Алгоритм построения и основные свойства ЕП- аппроксимации в тензорном произведении гильберто вых пространств
- Анализ эффективности ЕП-приближений случайных матриц
- Основные сведения из теории сплайн-аппроксимации на двумерных хаотических сетках
- Статистический анализ эффективности ЕП-приближений на двумерных хаотических сетках.
Введение к работе
В-задачах численного анализа, в которых участвуют в качестве исходных данных или в качестве искомого результата функции многих переменных, одна из проблем, с которой приходится сталкиваться, заключается в сложности анализа функциональных зависимостей подобного рода. Это могут быть сложные формульные зависимости, не поддающиеся упрощению, либо табличные данные, требующие дополнительной аппроксимации для выполнения типовых операций анализа (интегрирование, дифференцирование, построение графических образов и так далее). Типовым способом решения этой задачи является аппроксимация сплайнами, обеспечивающая простое локальное представление данных с допустимой потерей точности. Однако даже такое представление может оказаться достаточно объемным. В этой связи для функций двух и более переменных представляются пере-спективными так называемые методы редукции размерности - приближение функции двух: и более переменных с помощью некоторой комбинации функций меньшего числа переменных.
В известных работах А.Н. Колмогорова и его учеников [1 - 3] была решена проблема представления функции многих переменных с помощью суперпозиций и сумм непрерывных функций меньшего числа переменных, а именно, была доказана следующая теорема.
I Теорема. При любом целом п > 2 существуют такие определенные на единичном отрезке Е1 = [0, 1] непрерывные действительные функции фрч(х), что каждая определенная на n-мерном единичном, кубе Еп непрерывная действительная функция /(a*i,. . ., хп) пред-ставима в виде f(xu...,xn) = 2Y:xq[trqMi q=l р=\
Введение. І 4 где функции Xq(y) действительны и непрерывны.
Однако представления подобного рода едва ли возможно использовать в приложениях, так как алгоритм получения подобных разложений с точки зрения вычислительной математики неконструктивен.
В связи с тем, что на ЭВМ наиболее удобными являются элементарные арифметические операции, естественно ограничить класс всевозможных комбинаций функций такими, в которых используются лишь операции сложения и умножения.Наиболее простыми комбинациями такого типа являются суммы функций одного переменного.
Проблема аппроксимации функций многих переменных суммами функций одного переменного рассматривалась в работах [4-6]. Однако такой способ приближения обладает одним весьма существенным недостатком. Дело в том, что величина погрешности
Е/ = min Ц/Oi, я2, - , ж„) - (fi(xi вполне определяется функцией / и не может быть сделана меньше наперед заданной величины.
В этом смысле приближение функции нескольких переменных произведениями функций одного переменного обладает преимуществом, поскольку для остатка ri{xux2 хп) = f{xux2y...,xn) -^1^1)^2) ... :^\хп) можно вычислить следующее наилучшее приближение: №(<гЛ. .,Л2)|
Г2(хиХ2,...,Хп) = ri(xi,X2,...,Xn) ->i fclM (ж2) '<Рп '(хп)-
При этом r2(xi,x2,...,xn)\\ =тт\\г1(хих2,... ,-хп) - Ц (р\ }(хі)\\ =
Введение. 5 = .Ц/(ЯЪ Ж2,...,ЖП) - П^^^'г) - П^!2)(жг)|| < г=1 г=1 < ||гі(жьх2,...,а;п)||. (0.1)
Таким образом, для достижения необходимой точности достаточно взять соответствующее число членов ряда ' її <р\%і) + П р?]Ы + + П Л<) + , (0-2) г'=1 г—1 г=1 который строится последовательным повторением процедуры (0.1).
Впервые разложение в билинейный ряд (0.2) функции двух переменных в средне-квадратичной норме было сделано, по-видимому, в работе Шмидта уже в 1907 году [7]. Основные результаты этой работы достаточно подробно изложены в учебнике по математическому анализу Гурса [8].
В течении некоторого времени метод разложения в билинейный ряд не находил практического применения. Вероятно по той причине, что вычисление функций, необходимых для построения разложения в билинейный ряд,с помощью тех средств, которыми прежде располагали математики, являлось достаточно трудоемким делом.
Затем в шестидесятых годах в связи с развитием мощной цифровой вычислительной техники интерес к этому аппарату приближения функций многих переменных возродился вновь [9, 10]. В работе [10] были повторены некоторые из результатов Шмидта и предложен метод для вычисления функций ряда. Кроме того, в ней содержатся примеры применения метода разложения в билинейный ряд для обработки изображений и фильтрации шумов.
Здесь следует отметить, что если в качестве функции двух пе-ременных рассматривать прямоугольную матрицу, то приближение вида (0.2) есть ни что иное, как скелетное (сингулярное) разложе- ниє матрицы (подробнее b скелетных разложениях можно прочитать, например, в учебнике Гантмахера [11]). Поэтому в современной тер-
Введение. б минологии функции Шмидта ряда (0.2) обычно называют сингулярными функциями.
Дальнейшие исследования приближений функций двух переменных суммами произведений функций одного переменного были на-правлены на построение общей теории приближений в произвольном тензорном произведении гильбертовых пространств [12 - 15].
В работах [12'- 14] был использован классический подход к построению ряда (0.2), берущий свое начало в уже упомянутой работе Шмидта. Разложение вида (0.2) строится на всем тензорном произведении гильбертовых пространств.
В работе [15] Василенко предложил алгоритм построения разложения вида (0.2) (в современной терминологии ЕП-аппроксимации), где слагаемые ряда являются элементами конечномерного подпространства. Данное обстоятельство позволило существенно упростить вычислительные процедуры получения слагаемых разложения. Именно этот алгоритм (назовем его приближением на подпространстве) и взят за основу в предлагаемой диссертационной работе. Более подробно основы теории ЕП-аппроксимации рассмотрены в главе 1.
Оптимальная ЕП-аппроксимация достаточно успешно применялась в различных задачах численного анализа. В частности, одной из областей применения ЕП-разложений была аппроксимация функций на двумерных прямоугольных сетках. При этом использовалось два подхода. Первый заключался в построении ЕП-аппроксимации таблицы сеточной функции (представлении таблицы в виде суммы произведений одномерных векторов) с последующей одномерной сплайн-интерполяцией. Второй подход заключался в построении ЕП-приближения непосредственно двумерного сплайна на прямоугольной сетке. Достаточно успешное применение ЕП-аппроксимации для приближения функций, заданных в узлах прямоугольной двумерной сетки, послужило толчком для исследования возможности применения ее
Введение. для аппроксимации функций, заданных в узлах хаотической сетки.
Практическое использование ЕП-приближений показало достаточную их эффективность. Однако до сих пор удовлетворительных аналитических или численных оценок эффективности получено не было.
Рассмотрим величину E„(f) = inf \\f(x,y) - ± аі(х)Му)\\ь3- (0-3)
В работе Шмидта [7] доказано, что нижняя грань в правой части (0.3) достигается на фундаментальных функциях Шмидта, т.е. где ifi, фі - фундаментальные функции Шмидта, /лг- - сингулярные числа интегрального оператора с ядром f(x,y).
Известно [12, 13, 15], что вопрос о погрешности приближения функции отрезком билинейного ряда тесно связан с сингулярными чилами /іг-, а именно г=1 Ці г=1 \-Ч
Таким образом, проблема сходимости билинейных рядов равносильна проблеме оценок роста сингулярных чисел интегральных операторов.
Автору данной работы не удалось получить аналитической оценки поведения сингулярных чисел в ряде (0.2). По-видимому, основной причиной сложности получения этих оценок является нелинейность отображения, сопоставляющего функции ее ЕП-ряд. Именно по этой причине вызвал интерес подход к анализу качества приближения с помощью билинейного ряда, предложенный в работе Поспелова [12]. Изложим кратко суть этого подхода.
Рассмотрим функции и конечного ранга п (т.е. билинейный ряд разложения вида (0.2) конечен). Каждой такой функции поставим в соответствие монотонную последовательность чисел
Введение. 8 di = А? > > dn = Xl Здесь Х{ - коэффициенты разложения функции иу т.е. и ^ Ьі<ріФі Н h К<РпФп-
При этом известно, что r(u)=:min||u-/^|| = (l-A?)1/2
Таким образом каждое множество Кп функций и, \\и\\ = 1 отображается в множество Qn векторов (e?i,..., dn), у которых Y^di = 1, rfi > > dn.
Обозначим это отображение символом Un. Определим на Кп оценоч- ную функцию следующим образом: v(iq с кп) = мадвд), где /л - мера Лебега на множестве 0„, нормированная так, что (i{Qn) = 1. . і
Пусть .ге>„ = {иєіП г(и)>є}.
В работе было приведено доказательство слеудющей теоремы: Теорема. Для всякого є > О A(-Fei„) -)-0, 71 -ЮО.
Фактически, теорему молено переформулировать следующим образом:
Теорема. Для всякого є > 0 вероятность того, что у случайно взятой из множества Кп функции ее остаток после приближения
Введение. 9 одним слагаемым билинейного ряда будет больше є, стремится к О при п —> со.
Автором диссертационной работы была предпринята попытка адаптировать результаты теоремы к алгоритму приближения на подпространстве. Однако более тщательное изучение подхода выявило некоторые его недостатки.
Во-первых, в оценочных формулах никак не отражены свойства отображения, сопоставляющего функции набор коэффициентов ЕП-разложения. Тем самым, нигде не использовалось свойство, что Ai,...,An являются сингулярными числами интегрального оператора.
Во-вторых, в предложенном методе оценки предполагается, что коэффициенты di,...,dn имеют равномерное распределение. Как будет показано далее в главе 1, это утверждение в общем случае не верно.
Кроме того, в данной работе была допущена техническая ошибка при вычислении меры [J,{{di > x}f]Q,n}y исказившая: итоговый результат.
Несмотря на указанные выше недостатки, идея использовать метод вероятностного анализа для оценки эффективности на некотором классе функций оказалась вполне жизнеспособной.
Первая глава диссертационной работы посвящена выводам формул для простой вычислительной процедуры, позволяющей получить численную оценку эффективности ЕП-приближений для класса матриц одинаковой размерности, имеющих нормальное распределение. При выводе формул использовались результаты из многомерного статистического анализа для случайных матриц. В дополнение приводятся результаты численных экспериментов для некоторых классов матриц.
Введение. 10
Во второй главе рассматривается проблема построения оптимальной ЕП-аппроксимации функций, заданных в узлах хаотической сетки. В первой части главы предлагается алгоритм построения ЕП-аппроксимации. Вторая часть посвящена методике получения оценок, подобных оценкам из первой главы, для ЕП-приближений функций, заданных в узлах хаотической двумерной сетки. Описана схема вычислительного процесса получения численных оценок. Так же, как и в первой главе, приводятся результаты проведенных численных экспериментов.
Алгоритм построения и основные свойства ЕП- аппроксимации в тензорном произведении гильберто вых пространств
Прежде чем приступить і к описанию методики получения оценок эффективности ЕП-приближений случайных матриц, приведем основные понятия и утверждения из общей теории ЕП-аппроксимации. При изложении будем опираться на работу [15]. Задача ЕП-аппроксимации в простой форме заключается в следу I ющем. Пусть /(я, у) - вещественная функция от двух переменных х и у. Мы хотим заменить эту функцию конечной суммой произведений функций от одной переменной и обеспечить необходимую точность приближения. I Пусть даны пх 1 пу 1 и некоторые области flx С Яп% &у С RUy Определим Гильбертовы пространства X{Q,X) и Y(Qy) вещественных функций от векторных аргументов х-Е Qx или у Є їу 4 соответственно. Пусть О = Qx X ily и тензорное произведение и, кроме того, гильбертово пространство, ЯВЛЯЮЩееСЯ [15] ПОЛНЫМ ПО Некоторой КрОСС-НОрме Z(tt)i Введем некоторые обозначения. Пусть Хп - n-мерное подпространство в X(QX) с базисом cpi(x),... , рп(х), Ym - п-мерное подпространство в Y(Qy) с базисом фі(у),..., фт{у)- Конечномерная ЕП-аппроксимация имеет следующий вид: Будем говорить, что это представление является приведенным, если и функции Фпд,..., ФП)5 и функции Фтод,..., Ф77г]8 линейно независи-мы. Более того, если эти системы функций ортогональны (в соответствующих скалярных произведениях), будем говорить, что ЕП-аппроксимация ортогональна. Как показано в работе [15], каждая приведенная ЕП-аппроксима-ция может быть преобразована в ортогональную. Разложим функции ФП)&(#) и ФтДу) по базисным функциям: 1.1.
Необходимые сведения Пусть f(x, у) принадлежит тензорному пространству Z(Q). Нам необходимо найти оптимальную ЕП-аппроксимацию путем минимизации нормы по коэффициентам-a) , p) . Как уже было сказано выше, не нарушая общности можно полагать, что Обозначим «( ) = (4 -..,0 ), /?(fc) = ( ,...,Д ). Л и В -матрицы Грама базисных элементов, т.е. Через F обозначим прямоугольную п х га-матрицу, состоящую из элементов Раскрывая скобки в выражении (1.2) и используя метод множителей Лагранжа получаем, :что решение исходной задачи минимизации функционала (1.2) сводится к решению обобщенной спектральной задачи: ife=l Обобщенная спектральная задача (1.5) с (n+ra) х (п+?7г)-матрицей может быть сведена к обычной спектральной задаче с п х п или т х m-матрицей. Сначала следует применить разложение Холесского к матрицам Грама А и В: где L и М - треугольные матрицы. После небольших преобразований приходим к обычной спектральной задаче [15] с п х n-симметричной неотрицательной матрицей. Если Л 0 и z -соответствующий собственный вектор, то дает решение спектральной задачи (1.5). Также имеет место следующая теорема [15] Теорема. Если /(ж, у) Є XnYm (f(x,y) = E-LiEjLi І№(Х) ФзЬ)) то ее оптимальная ЕП-аппроксимация равна /(ж, у) для некоторого s mm{n, m} В дальнейшем будет предполагаться, что базисы подпространств ортонормированы. Это означает, что матрицы А и В - единичные. В этом случае очевидно, что набор собственных значений Лі,..., Л„ есть ни что иное, как набор сингулярных чисел матрицы F, а наборы векторов щ,..., ип и г і,..., vn её сингулярные векторы. При этих условиях предыдущая теорема напрямую следует из теоремы о сингулярном (скелетном) разложении матрицы. Кроме того, справедливо равенство: Помимо сведений из общей теорий ЕП-аппроксимации нам в дальнейшем понадобятся некоторые утверждения из теории случайных величин и векторов.
Первая лемма касается распределения линейной комбинации нормальных случайных величин. Лемма 1.1. Если случайные величины j,..., п имеют нормальные распределения, то величина = aii + + апп имеет нормальное распределение с математическим ожиданием и дисперсией, определяемыми формулами: где - коэффициент корреляции между величинами г- и &. В случае, когда величины , и & независимы, /9 = ( - символ Кронекера). Для получения формул, упрощающих моделирование полученного в следующем пункте распределения набора сингулярных чисел матрицы, нам понадобится следующая лемма. Лемма 1.2. Для плотности /(#i,..., a n) случайного вектора = (ъ і п) справедливо представление Далее приведены необходимые утверждения из теории случайных матриц. Определение. Случайная матрица Z есть матрица
Анализ эффективности ЕП-приближений случайных матриц
В данном пункте излагается методика получения численных показателей эффективности ЕП-разложения для случайных матриц. Под эффективностью алгоритма будет пониматься следующее: сколько чле-нов ЕП-разложения необходимо взять, чтобы с заданной вероятно і стью достигнуть требуемой точности приближения Пусть функция / Є Z(Q), где Z(Q) определена по формуле (1.1). Для определенности будем считать, что п т. Введем отображение где Мпхт - пространство матриц размера пхт, а матрица F вычислена по формуле (1І4). Несложно заметить, что элементы матрицы F - это ни что иное, как коэффициенты Фурье при разложении проекции функции / на подпространство X(Qn)Y(Q,m) по базису этого подпространства. Введем классы матриц: независимы} MF = {G Є Mnxm\ G = F + E, Є MJ. С классом Mp связан класс функций Иными словами, любая функция из класса Cf получается путем возмущения коэффициентов матрицы "эталонной" функции / по гауссов-скому закону. На таком классе и будем вести анализ эффективности алгоритма ЕП-аппроксимации. Пусть / - "эталонная" функция, a Cf - связанный с ней класс функций. Предположим, что мы хотим с помощью алгоритма ЕП-аппроксимации уменьшить объем хранимой информацию о функции geCf. Применим ЕП-разложение к функции h = д — /. Пусть Н = Q{h). Очевидно, что Я = G - F. Пусть УХ Є Мпхт \\Х\\\уг = Предположим, что мы построили ЕП-разложение для матрицы Н (а значит и для функции h): Д11мя є.
Возникает вопрос, можно ли утверждать, что є. Иными словами, насколько обоснованно мы можем утверждать, что получив с некоторой точностью приближение для матрицы Я и добавив его к образу "эталонной" функции мы получим приближение с необходимой точностью матрицы G. Преобразуем правую часть неравенства: Очевидно, что при Яд - /H lljvf 1 неравенство (1.10) выполнено. Найдем вероятность этого события (Я - некоторая случайная матрица из класса Ма). Имеем: Тогда по лемме 1.1 случайная величина т/ имеет стандартное нормальное распределение. Следовательно, искомая вероятность равна Вычислить эту вероятность можно с помощью таблиц для функции J I стандартного нормального распределения. При этом очевидно, что - і V [ для достаточно большого значения нормы -F f эта вероятность будет достаточно высокой. Далее все исследования будем проводить на классе матриц Ма. Теперь найдем распределение коэффициентов Лі,..., Л„ ЕП-аппрокси-мации (1.9) для Н Є Ма. Из независимости коэффициентов следует, что плотность распределения матрицы 5 Є Mo ri т где tr(XX ) след матрицы XX . Таким образом, плотность РЕ{Х) = р(ХХ ) является функцией от XX и, следовательно, к ней применима лемма . Пусть 0 = ЕЕ . Тогда по лемме 1.3 имеем: Вспомним, что в оценках точности приближения фигурируют квадраты коэффициентов ЕП-разложения (1.6). Следовательно, для получения оценок нам необходимо найти распределение собственных значений матрицы в, так как эти собственные значения являются квадра і тами сингулярных чисел (а значит, и коэффициентов ЕП-разложения) матрицы Е. Пусть /ii,..., /іп - собственные значения матрицы G. Как известно из линейной алгебры tr(Q) — =1 /І;, а 0 = П"=іА - Таким образом, мы получили, что PQ(Y) = q{y\, , уп)- гДе Уь , Уп - собственные значения матрицы У. Так как плотность распределения матрицы Y у Ре (У) является функцией от своих собственных значений, то применима теорема 1.1.
По теореме 1.1 плотность распределения собственных значений имеет вид: Далее, используя формулу (1.11), построим конструктивный вычислительный алгоритм для получения численных оценок эффективности ЕП-приближений на рассматриваемом классе матриц. Пусть дана требуемая точность приближения є и вероятность ро, с которой необходимо достигнуть этой точности. Численную оценку необходимого числа членов ЕП-аппроксимации можно получить следующим способом: 1) смоделировать набор векторов /2 = (/.q ,..., р\У), I = 1,..., iV, имеющих плотность распределения qfiu...tfin(yi,- -,Уп) (один из возможных способов моделирования описан далее); 2) для 5 = 1,...,7 — 1 вычислить Ns - количество векторов, для которых выполнено неравенство 3) в качестве оценки необходимого числа членов ЕП-аппроксима ции взять наименьшее s для которого Ns/N р$. При моделировании случайного вектора квадратов коэффициентов
Основные сведения из теории сплайн-аппроксимации на двумерных хаотических сетках
Прежде чем приступить к непосредственному описанию алгоритма Q построения ЕП-аппроксимации, приведем некоторые сведения из общей теории приближений на хаотической двумерной сетке. За основу возьмем алгоритм построения сплайна на ха ; I X Рисунок 1. Хаотическая сетка узлов. отических данных, основанный на методе функций Грина. Пусть Q - прямоугольная область в ТВ2. Пусть {Pi = (ж,-, уі), і = 1,...,5} - некоторая хаотическая сетка узлов в данной области, не лежащих на одной прямой (рисунок 1). Предположим, что в узлах этой сетки заданы значения Z{. Решение задачи построения сплайна в пространстве D 2Ь2(Ш2), удовлетворяющего интерполяционным условиям имеет вид ([15]): где Тогда коэффициенты разложения (2.1) находятся из системы уравнений реализации и универсален. Для решения системы (2.2) можно применять метод Гаусса с выбором главного элемента, метод вращений и т.д. Решение системы выполняется за 0(iV3) действий, а процедура расчета значения сплайна в точке требует O(N) действий. Здесь следует отметить, что из-за плотной матрицы и достаточно дорогой процедуры расчета значения сплайна в точке возможности данного алгоритма весьма ограничены. В случае, когда число узлов сетки достаточно велико, вместо этого алгоритма лучше использовать алгоритмы, базирующиеся на методе конечных элементов или на разбиении исходйой задачи на подзадачи. Однако при относительно небольшом числе узлов хаотической сетки (« 100) данный алгоритм существенно эффективней метода конечных элементов. В дальнейшем в работе мы будем опираться на приведенный алгоритм построения сплайна.
В случае, когда требуются массированные расчеты значений сплайна в точках, для уменьшения числа операций обычно сначала выполняют пересчет полученного сплайна на прямоугольную сетку, а затем осуществляют интерполяцию на двумерной сетке, используя, например, бикубический сплайн. Первоначально постановка задачи построения ЕП-аппроксимации на двумерной хаотической сетке звучала следующим образом. Пусть П - прямоугольная область в И2 с заданной на ней прямоугольной сеткой с узлами х\,...,хм и у\,...,ум- Пусть Рг-, г — 1,...,5 - некоторая хаотическая сетка узлов в данной области, не лежащих на одной прямой. Предположим, что в узлах этой сетки заданы значения Z{. Обозначим через Фх пространство конечных элементов, связанных с сеткой 1,...,хм, с базисом {ірі,...,(рмФ}, а через Фу - пространство конечных элементов, связанных с сеткой і/і,..., ум, с базисом По аналогии с общей теорией ЕП-аппроксимации необходимо найти такую функцию Однако найти простого с вычислительной точки зрения решения (как в случае общей теории ЕП-аппроксимации) не удалось. Это, главным образом, связано с. тем, что пространство функций, заданных в узлах хаотической сетки, не является тензорным. А именно это свойство и позволило в общей теории ЕП-аппроксимации свести решение опти і мизационной задачи к решению обобщенной спектральной задачи. В связи с вышеизложеннным было решено отказаться от попыток построения ЕП-аппроксимации, используя напрямую значения функции в узлах хаотической сетки.
В предыдущем пункте был описан известный и достаточно популярный алгоритм построения сплайн-аппроксимации функции, заданной в узлах хаотической сетки. При этом хранение коэффициентов сплайна (в случае, когда количество узлов хаотической сетки достаточно велико и, следовательно, желателен пересчет сплайна на прямоугольную сетку с последующей переинтерполяцией) может потребовать достаточно большого количества памяти ЭВМ. Предлагаемый в работе алгоритм построения ЕП-ряда, интерполирующего значения сеточной функции, заданной в узлах Р\1... ,Ps, имеет целью уменьшение количества хранимых коэффициентов. Мы хотим построить ЕП-приближение сплайна на хаотической сетке (2.1) в пространстве Z = Фх 8 Фу Иными словами, оптимальное приближение к сплайну (2.1) будем искать в виде ряда:
Статистический анализ эффективности ЕП-приближений на двумерных хаотических сетках.
Предлагаемый пункт диссертационной работы посвящен анализу эффективности ЕП-аппроксимации функций, заданных в узлах хаотической сетки. В главе 1 был проведен анализ эффективности ЕП-приближений случайных матриц. При некотором предположении о плотности распределения матрицы был) получен простой конструктивный алгоритм вычисления необходимого количества слагаемых ЕП-ряда для достижения требуемой точности приближения при заданной доверительной вероятности. Этого удалось достичь благодаря получению совместного распределения коэффициентов ЕП-ряда с последующим разложением его в произведение более простых одномерных распределений. В данной главе показателем эффективности ЕП-аппроксимации, также как и в первой главе, будет необходимое количество слагаемых ряда, необходимых для достижения требуемой точности при заданной доверительной вероятности.
В отличие от главы 1, получение аналитического представления плотности распределения коэффициентов ЕП-ряда в случае аппроксимации функции, заданной в узлах хаотической сетки, вызвало достаточно большие затруднения. Вспомним, что в первой главе простота формулы плотности распределения решения спектральной задачи была следствием специфич - ! ности плотности распределения матрицы F системы (1.5). В условиях главы 2 добиться такой постановки задачи анализа эффективности ЕП-аппроксимации, при которой элементы уже упомянутой матрицы F имели бы как и в первой главе независимые оди-наковые нормальные распределения, не представляется возможным. Поэтому идеология, основанная на утверждениях из теории многомерных распределений и случайных матриц ([1,3]), не приводит к результату, сопоставимому по простоте использования с формулами из главы 1 - результирующие формулы оказывались весьма громоздкие и практически не пригодные для анализа. В итоге было принято решение выполнить серию полных расчетов ЕП-аппроксимации со случайными входными данными. Затем провести статистический анализ полученных результатов аналогично главе 1. Далее изложим описание методики проведения численных экспериментов. Зафиксируем в пространстве Ж прямоугольную сетку с узлами #1,..., хк и г/і,..., ум- Моделируем 5 узлов хаотической сетки, равномерно распределенных в прямоугольнике [гсі,а;дг] х [уі,ум]- На этом подготовительные оперцйи завершены. Далее полученные сетки будут участвовать в серии экспериментов. На первом этапе выполняется формирование исходных данных для построения ЕП-аппроксимации. Для этого моделируем случайный вектор значений в узлах хаотической сетки, при условии его равномерного распределения на 5-мерной единичной сфере. Способы моделирования достаточно подробно изложены в работе [19]. На втором этапе строим глобальный сплайн, аппроксрімирующий значения в узлах хаотической сетки. Параллельно вычисляем ЕП-аппроксимацию на хаотической сетке по алгоритму, описанному в предыдущем пункте. На последнем этапе для каждой Построение базиса пространства сплайнов і Формирование очередного сплайна Вычисление ІЛ-разложеніїя частичной суммы ЕП-ряда вычи сляется норма разности со сплай ном (2.1). Полученная норма раз ности и является элементом вы борки для последующего стати стического анализа. Для получения статисти Вычисление погрешности приближения т да Пр одолжить н а6ор"""---..:. --._ статистики? ,.--- " нет Завершение
Рисунок 2. Блок-схема. ческой выборки следует повторить описанные выше пункты необходимое количество раз. Описанная выше методика была положена в основу разработанного программного обеспечения для проведения тестовых рас-счетов. Блок-схема тестовой программы приведена на рисунке 2. Для уменьшения объема вычислений на первом этапе формируется базис в пространстве сплайнов на хаотической двумерной сетке. В качестве базисных функций ис-пользуются сплайны, принимающие в одном из узлов значение 1, а в остальных узлах хаотической сетки нулевые значения. Благодаря этому нет необходимости для каждого нового набора значений на хаотической сетке вычислять глобальный сплайн. По описанной методике был проведен ряд численных экспериментов. В качестве базисов пространств Ф и Фу были выбраны набо ч ры 5-сплайнов третьей Степени, связанные с одномерными сетками #i,.. ., хм и /1,. .., ум- Расчет скалярных произведений (2.4) и итого вой разности между частичными суммами ЕП-ряда и сплайном (2.1) осуществлялся в норме JL/2 на более мелкой сетке с использованием метода трапеций. В качестве примера (см. приложение 2) продемонстрируем результаты экспериментов в случае, когда количество узлов прямоугольной сетки по каждой из переменных N = М = 50, количество узлов хаотической сетки S = 100. Если сравнить качество приближения функции, заданной в узлах хаотической сетки с помощью ЕП-аппроксимации, с моделью, рассматриваемой в главе 1, то мы увидим, что реальная скорость сходимости ЕП-ряда к сплайну заметно выше, чем предсказывала модель в главе 1. Обсудим это расхождение. Если внимательно посмотреть на постановку задачи в главе 1, то мы увидим, что фактически мы пытаемся с помощью алгоритма ЕП-аппроксимации получить приближение матриц всевозможного вида (в том числе и так называемого "белого шума"). В условиях же главы 2 осуществляется построение оптимальной ЕП-аппроксимаций для некоторого класса сплайнов на хаотической сетке. При этом очевидно, что между элементами матрицы F в обобщенной спектральной задаче (1.5) существует (в отличие от главы 1) функциональная зависимость.
По мнению автора, именно это обстоятельство, главным образом, влияет на качество ЕП-приближений. В пользу этого говорит результаты практического использования алгоритма ЕП-аппроксимации в различных приложениях. Вспомним, I что погрешность приближения вполне определяется собственными і значениями из спектральной задачи (1.5). Как правило, картина распределения этих собственных значений была следующей. Первое собственное значение (иногда первые два) достаточно большое. Как пра вило, первое (первые два) слагаемое обеспечивает приближение на 80-90%. Далее следует группа (5-10) собственных значений заметно меньших по величине, но тем не менее еще дающих некоторый вклад в уменьшение погрешности приближения. Все остальные собствен-ные значения пренебрежимо малы. В главе 1 был дан простой конструктивный алгоритм, предназначенный для анализа эффективности ЕП-аппроксимации случайных матриц. На основе приведенного алгоритма было разработано программное обеспечение. В; данном приложении приводятся некоторые результаты проведенных численных экспериментов. Пример 1. В первом примере рассматривались матрицы размерностью 50 х 51. Как уже было сказано в главе 1, все элементы матрицы независимы и имеют нормальное распределение с одинаковой дисперсией. В предлагаемом примере мы предполагаем, что дисперсия о1 = 1. В таблице приведено необходимое (вычисленное с помощью алгоритма, описанного в главе 1) количество слагаемых ЕП-ряда, чтобы достигнуть заданной относительной погрешности є с заданной доверительной вероятностью р. На гистограммах отображены выборочные распределения относительных ошибок приближений для разного числа слагаемых ЕП-ряда. Горизонтальная шкала гистограмм представляет область возможных относительных ошибок (от 0 до 1) и разбита на 20 групп по 0.05. Высота столбцов (вертикальная шкала) отбражает процент попадания ошибок в ту или иную группу. Общее количество отсчетов равно 200.
