Исследование составляющих ошибки для решения обратной задачи с использованием случайных проекций
Проведен сравнительный анализ решений дискретных некорректных обратных задач, полученных в результате оцифровки интегрального уравнения (задача Carasso, Delves, Phillips). Использовались методы псевдообращения и регуляризации Тихонова и эти же методы с использованием дополнительного проецирования сл...
Збережено в:
| Опубліковано в: : | Математичні машини і системи |
|---|---|
| Дата: | 2010 |
| Автор: | |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Інститут проблем математичних машин і систем НАН України
2010
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/83311 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Исследование составляющих ошибки для решения обратной задачи с использованием случайных проекций / Е.Г. Ревунова // Мат. машини і системи. — 2010. — № 4. — С. 33-42. — Бібліогр.: 22 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-83311 |
|---|---|
| record_format |
dspace |
| spelling |
Ревунова, Е.Г. 2015-06-18T09:44:03Z 2015-06-18T09:44:03Z 2010 Исследование составляющих ошибки для решения обратной задачи с использованием случайных проекций / Е.Г. Ревунова // Мат. машини і системи. — 2010. — № 4. — С. 33-42. — Бібліогр.: 22 назв. — рос. 1028-9763 https://nasplib.isofts.kiev.ua/handle/123456789/83311 004.942 + 623.454.862 Проведен сравнительный анализ решений дискретных некорректных обратных задач, полученных в результате оцифровки интегрального уравнения (задача Carasso, Delves, Phillips). Использовались методы псевдообращения и регуляризации Тихонова и эти же методы с использованием дополнительного проецирования случайной матрицей. Исследована зависимость составляющих ошибки решения (смещение и дисперсия) от размерности матрицы проектора. При использовании проецирования, метод псевдообращения продемонстрировал точность на уровне регуляризации Тихонова. Проведено порівняльний аналіз рішень дискретних некоректних зворотних задач, отриманих у результаті дискретизації інтегрального рівняння (задача Carasso, Delves, Phillips). Використовувалися методи псевдозвернення і регуляризації Тихонова і ці ж методи з використанням додаткового проектування випадковою матрицею. Досліджено залежність складових помилки рішення (зсув і дисперсія) від розмірності матриці проектора. При використанні проектування метод псевдозвернення продемонстрував точність на рівні регуляризації Тихонова. A comparative analysis of discrete ill-posed inverse problems solutions obtained by discretization of the integral equation (Carasso, Delves, Phillips problems) has been performed. Pseudo-inverse and Tikhonov regularization methods were used. The same technique we used with additional projection by random matrix. The error partitioning into bias and variance was done. The dependence of the components of error solution (bias and variance) on the dimension of the projector matrix was studied. Pseudo-inverse method, when projecting, has shown the accuracy similarly to Tikhonov regularization. ru Інститут проблем математичних машин і систем НАН України Математичні машини і системи Обчислювальні системи Исследование составляющих ошибки для решения обратной задачи с использованием случайных проекций Дослідження складових помилки для вирішення зворотної задачі з використанням випадкових проекцій Study error components for solving the inverse problem using random projections Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
Исследование составляющих ошибки для решения обратной задачи с использованием случайных проекций |
| spellingShingle |
Исследование составляющих ошибки для решения обратной задачи с использованием случайных проекций Ревунова, Е.Г. Обчислювальні системи |
| title_short |
Исследование составляющих ошибки для решения обратной задачи с использованием случайных проекций |
| title_full |
Исследование составляющих ошибки для решения обратной задачи с использованием случайных проекций |
| title_fullStr |
Исследование составляющих ошибки для решения обратной задачи с использованием случайных проекций |
| title_full_unstemmed |
Исследование составляющих ошибки для решения обратной задачи с использованием случайных проекций |
| title_sort |
исследование составляющих ошибки для решения обратной задачи с использованием случайных проекций |
| author |
Ревунова, Е.Г. |
| author_facet |
Ревунова, Е.Г. |
| topic |
Обчислювальні системи |
| topic_facet |
Обчислювальні системи |
| publishDate |
2010 |
| language |
Russian |
| container_title |
Математичні машини і системи |
| publisher |
Інститут проблем математичних машин і систем НАН України |
| format |
Article |
| title_alt |
Дослідження складових помилки для вирішення зворотної задачі з використанням випадкових проекцій Study error components for solving the inverse problem using random projections |
| description |
Проведен сравнительный анализ решений дискретных некорректных обратных задач, полученных в результате оцифровки интегрального уравнения (задача Carasso, Delves, Phillips). Использовались методы псевдообращения и регуляризации Тихонова и эти же методы с использованием дополнительного проецирования случайной матрицей. Исследована зависимость составляющих ошибки решения (смещение и дисперсия) от размерности матрицы проектора. При использовании проецирования, метод псевдообращения продемонстрировал точность на уровне регуляризации Тихонова.
Проведено порівняльний аналіз рішень дискретних некоректних зворотних задач, отриманих у результаті дискретизації інтегрального рівняння (задача Carasso, Delves, Phillips). Використовувалися методи псевдозвернення і регуляризації Тихонова і ці ж методи з використанням додаткового проектування випадковою матрицею. Досліджено залежність складових помилки рішення (зсув і дисперсія) від розмірності матриці проектора. При використанні проектування метод псевдозвернення продемонстрував точність на рівні регуляризації Тихонова.
A comparative analysis of discrete ill-posed inverse problems solutions obtained by discretization of the integral equation (Carasso, Delves, Phillips problems) has been performed. Pseudo-inverse and Tikhonov regularization methods were used. The same technique we used with additional projection by random matrix. The error partitioning into bias and variance was done. The dependence of the components of error solution (bias and variance) on the dimension of the projector matrix was studied. Pseudo-inverse method, when projecting, has shown the accuracy similarly to Tikhonov regularization.
|
| issn |
1028-9763 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/83311 |
| citation_txt |
Исследование составляющих ошибки для решения обратной задачи с использованием случайных проекций / Е.Г. Ревунова // Мат. машини і системи. — 2010. — № 4. — С. 33-42. — Бібліогр.: 22 назв. — рос. |
| work_keys_str_mv |
AT revunovaeg issledovaniesostavlâûŝihošibkidlârešeniâobratnoizadačisispolʹzovaniemslučainyhproekcii AT revunovaeg doslídžennâskladovihpomilkidlâviríšennâzvorotnoízadačízvikoristannâmvipadkovihproekcíi AT revunovaeg studyerrorcomponentsforsolvingtheinverseproblemusingrandomprojections |
| first_indexed |
2025-11-24T08:24:38Z |
| last_indexed |
2025-11-24T08:24:38Z |
| _version_ |
1850843861462548480 |
| fulltext |
© Ревунова Е.Г., 2010 33
ISSN 1028-9763. Математичні машини і системи, 2010, № 4
УДК 004.942 + 623.454.862
Е.Г. РЕВУНОВА
ИССЛЕДОВАНИЕ СОСТАВЛЯЮЩИХ ОШИБКИ ДЛЯ РЕШЕНИЯ ОБРАТНОЙ
ЗАДАЧИ С ИСПОЛЬЗОВАНИЕМ СЛУЧАЙНЫХ ПРОЕКЦИЙ
Анотація. Проведено порівняльний аналіз рішень дискретних некоректних зворотних задач,
отриманих у результаті дискретизації інтегрального рівняння (задача Carasso, Delves, Phillips).
Використовувалися методи псевдозвернення і регуляризації Тихонова і ці ж методи з
використанням додаткового проектування випадковою матрицею. Досліджено залежність
складових помилки рішення (зсув і дисперсія) від розмірності матриці проектора. При
використанні проектування метод псевдозвернення продемонстрував точність на рівні
регуляризації Тихонова.
Ключові слова: дискретна некоректна зворотна задача, псевдозвернення, регуляризація,
проектування, зсув, дисперсія.
Аннотация. Проведен сравнительный анализ решений дискретных некорректных обратных
задач, полученных в результате оцифровки интегрального уравнения (задача Carasso, Delves,
Phillips). Использовались методы псевдообращения и регуляризации Тихонова и эти же методы с
использованием дополнительного проецирования случайной матрицей. Исследована зависимость
составляющих ошибки решение (смещение и дисперсия) от размерности матрицы проектора.
При использовании проецирования метод псевдообращения продемонстрировал точность на
уровне регуляризации Тихонова.
Ключевые слова: дискретная некорректная обратная задача, псевдообращение, регуляризация,
проецирование, смещение, дисперсия.
Abstract. A comparative analysis of discrete ill-posed inverse problems solutions obtained by
discretization of the integral equation (Carasso, Delves, Phillips problems) has been performed. Pseudo-
inverse and Tikhonov regularization methods were used. The same technique we used with additional
projection by random matrix. The error partitioning into bias and variance was done. The dependence of
the components of error solution (bias and variance) on the dimension of the projector matrix was
studied. Pseudo-inverse method, when projecting, has shown the accuracy similarly to Tikhonov
regularization.
Key words: discrete ill-posed inverse problems, pseudoinverse, regularization, projection, bias, variance.
1. Введение
Во многих практических приложениях требуется решать дискретную обратную задачу
вида
где матрица NNΦ ×ℜ∈ и вектор Ny ℜ∈ , искаженный аддитивным шумом Nε ℜ∈ εyy += 0 ,
известны и получены в результате оцифровки интегрального уравнения первого рода [1–
3]. Требуется оценить вектор сигнала Nx ℜ∈ .
В случае, когда y содержит шум, ряд сингулярных чисел iσ матрицы Φ плавно
спадает к нулю, Φ имеет высокое число обусловленности minmax /σσ , задачу оценки x
называют дискретной некорректной обратной задачей [1]. Такие свойства Φ характерны
для задач спектрометрии [4], гравиметрии [5], электроразведки [6].
Решение дискретной некорректной обратной задачи как задачи наименьших
квадратов [7]
yΦx = , (1)
2
minargˆ Φxyx
x
−= (2)
34 ISSN 1028-9763. Математичні машини і системи, 2010, № 4
на основе псевдообращения
является неустойчивым [1, 2]. Признаком неустойчивости является то, что малым
изменениям вектора y соответствуют большие изменения решения x̂ ; при этом велико
значение ошибки решения.
Для преодоления неустойчивости и, соответственно, повышения точности решения
используют регуляризацию [1–3, 7]. Регуляризация накладывает некоторые ограничения
на решения, которые позволяют повысить их устойчивость, например, малость l2-нормы
решения
2
x̂ . Классическим методом регуляризации является регуляризация Тихонова [1].
Задачу регуляризации Тихонова формулируют следующим образом:
22
minargˆ xxΦyx
x
λ+−= , (4)
где λ – параметр регуляризации.
Недостатками, присущими методам решения дискретных некорректных обратных
задач на основе регуляризации Тихонова, являются высокая вычислительная сложность и
сложность подбора правильного параметра регуляризации, от которого в значительной
мере зависит устойчивость решения. Поэтому востребованными являются альтернативные
подходы к решению дискретной некорректной обратной задачи с точностью на уровне
регуляризации Тихонова, но с меньшей вычислительной сложностью.
Нами разрабатывается подход к решению дискретной некорректной обратной
задачи с использованием методов псевдообращения и случайных проекций [8, 9]. В данной
работе приводятся результаты исследования составляющих ошибки решения, полученные
данным подходом, и их сравнение с ошибкой традиционных подходов. В качестве
экспериментального материала используются известные примеры обратных задач [10–12].
Показано убывание составляющей смещения и рост составляющей дисперсии ошибки
решения с ростом размерности проекционной матрицы, наличие минимума ошибки и
возможность получения решения с хорошей точностью без использования регуляризации
Тихонова.
2. Решение дискретной некорректной обратной задачи методом случайных проекций
Нами разрабатывается подход к решению дискретной некорректной обратной задачи,
использующий проекционную версию рандомизированных алгоритмов приближения
матриц [13]. В качестве проектора NkR ×ℜ∈ используется матрица с элементами,
сформированными реализациями случайной величины [14, 15]. Случайные проекционные
матрицы с Nk < используются также в теории [16, 17] и практике [18] вложений
векторных пространств (vector space embeddings) для сокращения размерности векторов с
целью ускорения оценки их сходства.
Для решения обратной задачи с использованием проекционного подхода [19]
умножим обе части исходного уравнения (1) на матрицу NkR ×ℜ∈ , Nk ≤ , элементы
которой – реализации случайной величины с нормальным распределением, нулевым
средним и единичной дисперсией. Число столбцов N матрицы R определяется
размерностью исходной матрицы Φ , число строк k априори не фиксировано.
Получим уравнение
bAx = , где RΦA = , NkA ×ℜ∈ , Ryb = , kb ℜ∈ . (5)
Тогда задача наименьших квадратов (2) записывается в виде
2
minargˆ bAxx
x
−= . (6)
yΦx +=ˆ (3)
ISSN 1028-9763. Математичні машини і системи, 2010, № 4 35
Восстановление сигнала x на основе псевдообращения получим как
bAx +=ˆ . (7)
Восстановление сигнала методом регуляризации Тихонова получим как
22
minargˆ xbAxx
x
λ+−= . (8)
Точность решения обратной задачи будем оценивать с помощью ошибки d
восстановления истинного сигнала x , вычисляемой как
exxd =−= ˆ , (9)
где x̂ – вектор восстановленного сигнала, e – вектор ошибки решения.
3. Составляющие ошибки восстановления истинного сигнала
Вектор ошибки e представляют [20, 21] в виде суммы двух составляющих: дисперсии и
смещения. Составляющие вычисляются следующим образом. Пусть P – оператор,
преобразующий y в x̂ (рис. 1): Pyx =ˆ , тогда, с учетом εyy += 0 , выражение для оценки
x можно представить в виде
ΡεΡΦxPεPyεyPx +=+=+= 00 )(ˆ ; Φxy =0 . (10)
Используя выражение для x̂ , получаем выражение для e :
ΡεxΙΡΦΡεxΡΦxxxe +−=+−=−= )(ˆ . (11)
Таким образом,
21 eee += , где Nee ℜ∈21, , xΙΡΦe )(1 −= , Ρεe =2 . (12)
1e называют смещением, 2e – дисперсией [20, 21].
Различным методам решения задачи (1) соответствуют операторы P разного вида.
На рис. 1 схематически показано действие:
– проектора R , преобразующего
вектор правой части y уравнения (1) в
вектор b ;
– оператора PrΡ , преобразующего b в
Prx̂ ;
– оператора Φ , преобразующего x в
y ;
– оператора P , преобразующего (10)
y в x̂ .
Для получения решения подходами
без проецирования будем использовать
следующие методы.
Решение на основе псевдообращения (3) (алгоритм [22])
yΦxpin
+= , T
iipin UdiagVΦΡ )/( σϕ== + при treshi >σ 1=iϕ , иначе 0=iϕ .
))(max(),max( iepsNktresh σ= ,
(13)
где U , V , S – результат сингулярного разложения матрицы TUSVΦ = ;
)(Sdiagi =σ – сингулярные числа, элементы диагональной матрицы S ;
)(aeps – положительное расстояние от )(aabs до следующего, большего по величине
числа с плавающей точкой, имеющего ту же точность, что и a .
Здесь разбиение ошибки имеет следующий вид:
P
R
Ф
PPr
y
x'Pr
b
x'
x
ℜN ℜN
ℜk
Рис. 1. Схема действия P , Φ , R , PrΡ
36 ISSN 1028-9763. Математичні машини і системи, 2010, № 4
xΙΦΡe pinpin )(1 −= , εΡe pinpin =2 . (14)
Решение на основе регуляризации по Тихонову (4) методом фильтрованного
сингулярного разложения [1]:
,)/( yUfdiagVx T
iireg σ= (15)
где )/( 222 λσσ += iiif – фильтрующие множители. Здесь
T
iireg UfdiagVΡ )/( σ= . (16)
Так как εΦxy += , то можно записать:
εΡxΙΦΡxεΦxΡxxe regregregregreg +−=−+=−= )()( , (17)
xΙΦΡe regreg )(1 −= , εΡe regreg =2 . (18)
После проецирования составляющие ошибки решения принимают следующий вид.
Аналогично (11), можно записать (рис. 1):
RεΡxΙRΦΡxεΦxRΡxRyΡxxe PrPrPrPrPrPr )()(ˆ ++=−+=−=−= . (19)
Для решения на основе псевдообращения:
T
iipin BsgdiagCΡ )/(Pr = при treshsi > 1=ig , иначе 0=ig ,
))(max(),max( isepsNktresh = ,
(20)
где B , C , Σ – результат сингулярного разложения матрицы TCBA Σ= , )(Σdiagsi = –
сингулярные числа, элементы диагональной матрицы Σ .
Составляющие ошибки:
xΙAΡe pinpin )( PrPr1 −= , RεΡe pinpin PrPr2 = ; PrPr2Pr1 pinpinpin eee =+ , (21)
где Prpine – ошибка решения для оценки вектора сигнала на основе псевдообращения с
использованием случайных проекций.
Для регуляризации Тихонова по методу фильтрованного сингулярного разложения
[1]:
T
iireg BsdiagCAΡ )/(Pr ϕ== + , (22)
где )/( 222 λϕ += iii ss – фильтрующие множители.
xΙAΡe regreg )( PrPr1 −= , RεΡe regreg PrPr2 = ; PrPr2Pr1 regregreg eee =+ , (23)
где Prrege – ошибка решения для оценки вектора сигнала на основе псевдообращения с
использованием случайных проекций.
4. Схема экспериментального исследования
Исследуем экспериментально:
– зависимость ошибки восстановления сигнала d от числа строк k матрицы
проектора R ;
– зависимость нормы каждой из составляющих ошибки 1e и 2e от k .
Используем данные известных дискретных некорректных обратных задач Carasso
[12], Delves [11] и Phillips [10].
Во всех задачах матрица Φ , полученная при оцифровке ядра, имела размерность
200×200, высокое число обусловленности )1/( minmax >>σσ и ряд сингулярных чисел,
плавно спадающий к нулю. Вектор правой части уравнения (2) после оцифровки
искажался аддитивным шумом ε c нормальным распределением.
ISSN 1028-9763. Математичні машини і системи, 2010, № 4 37
0.01
0.1
1
10
100
1000
0 50 100 150 200
k
d
reg2 lcur 1e-8
reg2 lcur 1e-6
reg2 lcur 1e-4
reg3 dsc 1e-8
reg3 dsc 1e-6
reg3 dsc 1e-4
pinv1 1e-8
pinv1 1e-6
pinv1 1e-4
Рис. 4. Зависимость ошибки восстановления
сигнала d от числа строк k матрицы проектора R
при уровнях шума 10–8, 10–6, 10–4 для задачи Carasso
а б в
Рис. 2. Матрица Φ для задачи: а – Carasso, б – Delves, в – Phillips
0
0,2
0,4
0,6
0,8
1
1 21 41 61 81 101 121 141 161 181
x
y
-0,02
-0,01
0
0,01
0,02
0,03
0,04
0,05
0,06
0,07
1 25 49 73 97 121 145 169 193
x
y
0,00E+00
5,00E-01
1,00E+00
1,50E+00
2,00E+00
2,50E+00
1 16 31 46 61 76 91 106 121 136 151 166 181 196
y
x
а б в
Рис. 3. Дискретно заданные сигнал x и правая часть y в задаче:
а – Carasso, б – Delves, в – Phillips
Для задачи Carasso матрица Φ получается из аналитически заданной функции ядра:
)(),( tsktsK −= , )
4
1
exp(
2
)(
2/1
2/3
t
t
tk −=
−
π
. (24)
На рис. 4 приведены зависимости ошибки восстановления сигнала d от числа строк
k матрицы проектора )( NkR × при
уровнях шума 10–8, 10–6, 10–4 для
методов:
– псевдообращения pinv1;
– регуляризации по Тихонову с
подбором λ по методу L -кривой reg2;
– с подбором λ по методу
обобщенной невязки reg3.
Анализ зависимостей d от k
показывает, что для всех методов при
определенном значении k зависимость
имеет минимум, положение которого
при возрастании уровня шума
смещается в область меньших значений
k , а значение ошибки в точке
минимума возрастает.
Значения ошибки для методов
без проецирования и минимальные
значения ошибки для методов с
проецированием приведены в табл. 1.
38 ISSN 1028-9763. Математичні машини і системи, 2010, № 4
1.E-04
1.E-03
1.E-02
1.E-01
1.E+00
1.E+01
1.E+02
1.E+03
0 50 100 150 200
k
d
pinv 1e-8
pinv 1e-6
pinv 1e-4
e1 pinv 1e-8
e2 pinv 1e-8
e1 pinv 1e-6
e2 pinv 1e-6
e1 pinv 1e-4
e2 pinv 1e-4
Рис. 5. Зависимости норм составляющих ошибки 1e
и 2e от k для метода псевдообращения в задаче
Carasso
Таблица 1. Значения ошибки для задачи Carasso
nl
Методы с проецированием Методы без проецирования
dmin pinv1 dmin reg2 dmin reg3 d pinv1 d reg2 d reg3
10–8 0,0136 0,0127 0,013 0,308 0,015 0,308
10–6 0,05 0,036 0,036 41,7 0,038 0,87
10–4 0,169 0,156 0,179 3000 0,18 0,66
Таким образом, среди методов без проецирования наименьшую ошибку
восстановления сигнала обеспечивает метод L -кривой reg2. Значения ошибки для метода
обобщенной невязки превышают ошибку метода L -кривой более чем в 20 раз при уровнях
шума 10–8, 10–6 и более чем в 3 раза при уровне шума 10–4. Значения ошибки для метода
псевдообращения pinv1 без проецирования при уровнях шума 10–6 и 10–4 высоки, что
свидетельствует о неустойчивости метода.
Для методов с проецированием значения ошибки в точке минимума mind сравнимы
и невелики, что свидетельствует об устойчивой работе методов. Метод обобщенной
невязки, демонстрировавший без проецирования высокие значения ошибки, после
проецирования дает ошибку на уровне метода L -кривой. Поведение метода
псевдообращения с проецированием становится устойчивым, и значения ошибки для него
– на уровне методов регуляризации Тихонова.
Чтобы понять поведение
зависимостей ошибки d от k для
разных методов, рассмотрим
зависимости норм составляющих
ошибки 1e и 2e (12) от k .
На рис. 5 – 7 приведены
зависимости d от k для pinv1, reg2, reg3
соответственно, e1 – зависимость 1e от
k , e2 – зависимость 2e от k . Для pinv1
1e и 2e вычислялись по формуле (21),
для reg2, reg3 – по формуле (23).
Из рис. 5 – 7 видно, что 1e
бывает с ростом k , а 2e растет. При
этом соотношение 1e и 2e таково, что
21 ee + имеет минимум. С возра-
станием уровня шума положение
минимума ошибки смещается в область
меньших значений k . Это происходит
вследствие того, что зависимость 1e от k неизменна для всех уровней шума (вектор
шума не входит в выражение для 1e ), а 2e растет с возрастанием уровня шума, вектор
которого входит в выражение для 2e как множитель.
Отличие reg2 и reg3 от pinv1 состоит в том, что зависимость rege1 от k не является
неизменной для всех уровней шума. Это происходит вследствие того, что параметр
ISSN 1028-9763. Математичні машини і системи, 2010, № 4 39
регуляризации, значение которого вычисляется для каждого k , входит в выражение для
rege2 и rege1 . Таким образом, оптимальность подбора λ влияет на значение ошибки в точке
минимума и на устойчивость метода.
Для задачи Delves матрицу Φ и вектор y получают дискретизацией аналитически
заданной функции ядра
На рис. 8 приведены зависимости ошибки восстановления сигнала d от числа строк k
матрицы проектора при уровнях шума 10–8, 10–6, 10–4 для методов pinv1, reg2, reg3.
Для всех методов зависимость d от k имеет минимум, положение которого при
возрастании уровня шума смещается в область меньших значений k , а значение ошибки в
точке минимума возрастает.
Значения ошибки для методов без проецирования и минимальные значения ошибки
для методов с проецированием приведены в табл. 2. Без проецирования метод
псевдообращения при уровнях шума 10–6, 10–4 ведет себя неустойчиво, что проявляется в
высоких значениях ошибки. После проецирования метод псевдообращения демонстрирует
устойчивое поведение и обеспечивает значения ошибки на уровне методов регуляризации.
Таблица 2. Значения ошибки для задачи Delves
nl
Методы с проецированием Методы без проецирования
dmin pinv1 dmin reg2 dmin reg3 d pinv1 d reg2 d reg3
10–8 0,0093 0,016 0,0095 0,01 0,024 0,0153
10–6 0,08 0,077 0,075 1,11 0,083 0,133
10–4 0,25 0,18 0,185 98,5 0,213 0,214
Для задачи Phillips матрица Φ получается из аналитически заданной функции ядра:
1.E-05
1.E-04
1.E-03
1.E-02
1.E-01
1.E+00
1.E+01
0 50 100 150 200
k
d
reg2 lcur 1e-8
reg2 lcur 1e-6
reg2 lcur 1e-4
e1 lcur 1e-8
e2 lcur 1e-8
e1 lcur 1e-6
e2 lcur 1e-6
e1 lcur 1e-4
e2 lcur 1e-4
1.E-04
1.E-03
1.E-02
1.E-01
1.E+00
1.E+01
1.E+02
1.E+03
0 50 100 150 200
k
d
reg3 dsc 1e-8
reg3 dsc 1e-6
reg3 dsc 1e-4
e1 dsc 1e-8
e2 dsc 1e-8
e1 dsc 1e-6
e2 dsc 1e-6
e1 dsc 1e-4
e2 dsc 1e-4
Рис. 6. Зависимости норм составляющих ошибки
1e и 2e от k для метода L -кривой в задаче
Carasso
Рис. 7. Зависимости норм составляющих
ошибки 1e и 2e от k для метода обобщенной
невязки в задаче Carasso
)1(),( −= tztzK при tz < , )1(),( −= zttzK при tz ≥ и 6/)()( 3 zzzr −= . (25)
)(),( tztzK −= φ , )
3
cos(1)(
x
x
πφ += при 3<x , 0)( =xφ при 3≥x , (26)
40 ISSN 1028-9763. Математичні машини і системи, 2010, № 4
Вектор y правой части (1) получен из )
3
sin(
2
9
))
3
cos(5,01)(6()(
zz
zzr
π
ππ ++−= .
На рис. 9 приведены зависимости d от k при уровнях шума 10–8, 10–6, 10–4 для
методов pinv1, reg2, reg3.
Значения ошибки для методов без проецирования и минимальные значения ошибки
для методов с проецированием приведены в табл. 3. Без проецирования при уровнях шума
10–6, 10–4 методы обобщенной невязки и псевдообращения ведут себя неустойчиво, что
проявляется в высоких значениях ошибки. После проецирования методы псевдообращения
и обобщенной невязки демонстрируют устойчивое поведение. Значения ошибки для
метода псевдообращения после проецирования сравнимы со значениями ошибки для
методов регуляризации. Как и в задачах Carasso и Delves, в задаче Phillips для всех методов
зависимость d от k имеет минимум, положение которого при возрастании уровня шума
смещается в область меньших значений k , а значение ошибки в точке минимума
возрастает.
Таблица 3. Значения ошибки для задачи Phillips
nl
Методы с проецированием Методы без проецирования
dmin pinv1 dmin reg2 dmin reg3 d pinv1 d reg2 d reg3
10–8 0,0007 0,000648 0,00064 0,0168 0,0006 0,0086
10–6 0,002 0,002 0,002 3,49 0,0017 1,19
10–4 0,021 0,0145 0,0217 104,35 0,011 0,899
5. Выводы
Проведено экспериментальное исследование методов решения дискретных некорректных
обратных задач (2), полученных в результате оцифровки ядра и правой части
интегрального уравнения первого рода. Сравнивались решения задач Carasso, Delves,
Phillips, полученные методом псевдообращения и регуляризацией Тихонова с подбором
0.01
0.1
1
10
100
0 50 100 150 200
k
d
reg2 lcur 1e-8
reg2 lcur 1e-6
reg2 lcur 1e-4
reg3 dsc 1e-8
reg3 dsc 1e-6
reg3 dsc 1e-4
pinv1 1e-8
pinv1 1e-6
pinv1 1e-4
0.0001
0.001
0.01
0.1
1
10
100
0 50 100 150 200
k
d
reg2 lcur 1e-8
reg2 lcur 1e-6
reg2 lcur 1e-4
reg3 dsc 1e-8
reg3 dsc 1e-6
reg3 dsc 1e-4
pinv1 1e-8
pinv1 1e-6
pinv1 1e-4
Рис. 8. Зависимость ошибки восстановления
сигнала d от числа строк k матрицы
проектора R при уровнях шума 10–8, 10–6, 10–4
для задачи Delves
Рис. 9. Зависимость ошибки восстановления
сигнала d от числа строк k матрицы проектора
R при уровнях шума 10–8, 10–6, 10–4 для задачи
Phillips
ISSN 1028-9763. Математичні машини і системи, 2010, № 4 41
параметра регуляризации по методу обобщенной невязки и L -кривой, и решения этими же
методами, но при использовании проецирования случайной матрицей )( NkR × .
Проведено разбиение ошибки решения на смещение 1e и дисперсию 2e .
Исследование поведения этих составляющих ошибки от числа строк k матрицы R
показало, что 1e убывает с ростом k , а 2e – растет. В рассмотренных задачах для
методов pinv2 и reg1 соотношение 1e и 2e таково, что 21 ee + имеет минимум. С
возрастанием уровня шума положение минимума ошибки смещается в область меньших
значений k и значение ошибки в точке минимума возрастает.
При надлежащем выборе k точность решения методом на основе псевдообращения
матрицы с проецированием для всех трех исследованных задач находится на уровне
лучшего метода регуляризации Тихонова без проецирования – с подбором λ по L-кривой
и в ряде случаев значительно превосходит точность регуляризации Тихонова с подбором
λ по методу обобщенной невязки. Проецирование в большинстве случаев снижает
ошибку решения регуляризацией Тихонова, особенно значительно – для случаев с
большой ошибкой решения до проецирования. Ошибка решения псевдообращением без
проецирования на несколько порядков превышает ошибки остальных методов, и метод
псевдообращения без проецирования не пригоден для решения рассмотренных обратных
задач.
Таким образом, изучение и использование методов на основе псевдообращения с
проецированием является перспективным в силу их устойчивости, проявляющейся в
плавном изменении относительной ошибки восстановления сигнала с ростом шума, а
также в силу снижения вычислительных затрат. Это снижение происходит из-за
уменьшения вычислительной сложности сингулярного разложения матрицы A при k ,
составляющих малую долю N (что особенно проявляется при увеличении уровня шума),
по сравнению со сложностью сингулярного разложения исходной Φ . Направлением
дальнейших исследований являются экспериментальные и теоретические методы
вычислительно-эффективного выбора размерности k проекционной матрицы R , при
которой достигается ошибка, близкая к минимальной.
СПИСОК ЛИТЕРАТУРЫ
1. Hansen P.C. Rank-deficient and discrete ill-posed problems. Numerical Aspects of Linear Inversion /
Hansen P.C. – SIAM, Philadelphia, 1998. – 247 p.
2. Тихонов А.Н. Методы решения некорректных задач / А.Н. Тихонов, В.Я. Арсенин. – М.: Наука,
1979. – 285 с.
3. Морозов В.А. Регулярные методы решения некорректно поставленных задач / Морозов В.А. –
М.: Наука, 1987. – 239 с.
4. Забулонов Ю.Л. Оптимизация решения обратной задачи по восстановлению функции плотности
распределения поверхностных загрязнений / Ю.Л. Забулонов, Ю.М. Коростиль, Е.Г. Ревунова //
Сборник научных трудов ИПМЭ НАН Украины “Моделирование и информационные технологии”.
– 2006. – C. 77 – 83.
5. Булах Е.Г. О новом аппроксимационном подходе к решению обратных задач гравиметрии в
классе трехмерных контактных поверхностей / Е.Г. Булах // Доклады НАНУ. – 2006. – № 1. –
С. 108 – 112.
6. Хмелевский В.К. Электроразведка / В.К. Хмелевский, В.М. Бондаренко. – М.: Недра, 1999. –
438 с.
7. Engl H.W. Regularization of inverse problems / Engl H.W., Hanke M., Neubaer A. – Dordrecht:
Kluwer Academic Publishers, 2000. – 321 p.
8. Candès E.J. Near optimal signal recovery from random projections: Universal encoding strategies? /
E.J. Candès, Т. Tao // IEEE Trans. Inf. Theory. – 2006. – Vol. 52, N 12. – P. 5406 – 5425.
42 ISSN 1028-9763. Математичні машини і системи, 2010, № 4
9. A Simple Proof of the Restricted Isometry Property for Random Matrices / R. Baraniuk, M. Davenport,
R. DeVore [et al.] // Constructive Approximation. – 2008. – Vol. 28, N 3. – P. 253 – 263.
10. Phillips D.L. A technique for the numerical solution of integral equation of the first kind // J.ACM. –
1962. – N 9. – P. 84 – 97.
11. Delves L.M. Computational methods for integral equations / L.M. Delves, Mohamed. – Cambridge:
Cambridge University Press, 1985. – 388 p.
12. Carasso A.S. Determining surface temperatures from interior observations / A.S. Carasso // SIAM
J.Appl.Math. – 1982. – N 42. – P. 558 – 574.
13. Halko N. Finding structure with randomness: Stochastic algorithms for constructing approximate
matrix decompositions / N. Halko, P.G. Martinsson, J.A. Tropp // ACM Report Caltech. – 2009. – N 5. –
P. 1 – 82.
14. Sarlos T. Improved approximation algorithms for large matrices via random projections / T. Sarlos //
Proc. of the 47th Annual IEEE Symposium on Foundations of Computer Science. – 2006. – P. 143 – 152.
15. Faster least squares approximation / P. Drineas, M.W. Mahoney, S. Muthukrishnan [et al.] // Tech.
Rep. 0710.1435. – 2007. – P. 1 – 19.
16. Rudelson M. Sparse Reconstruction by Convex Relaxation: Fourier and Gaussian Measurements /
M. Rudelson, R. Veshynin // CISS 2006 (40th Annual Conference on Information Sciences and Systems).
– P. 207 – 212.
17. Johnson W.B. Extensions of Lipschitz mappings into a Hilbert space / W.B. Johnson, J. Lindenstrauss
// Contemporary Mathematics. – 1984. – N 26. – P. 189 – 206.
18. Мисуно И.С. Векторные и распределенные представления, отражающие меру семантической
связи слов / И.С. Мисуно, Д.А. Рачковский, С.В. Слипченко // Математичні машини і системи. –
2005. – № 3. – С. 50 – 67.
19. Ревунова Е.Г. Повышение точности решения обратной задачи с использованием случайных
проекций / Е.Г. Ревунова, Д.А. Рачковский // International Conference "Knowledge-Dialogue-Solution"
(KDS-2). – 2009. – Р. 93 – 98.
20. Vogel C.R. Computational methods for inverse problems / Vogel C.R. – Philadelphia: SIAM, 2002. –
183 p.
21. Goldenshluger A. Adaptive estimation of linear functionals in Hilbert scales from indirect white noise
observations / А. Goldenshluger, S.V. Pereverzev // Probab. Theory Relat. Fields. – 2000. – N 118. –
P. 169 – 186.
22. LAPACK User's Guide / Anderson E., Bai Z., Bischof C. [et al.]. – Philadelphia: Third Edition,
SIAM, 1999. – 407 p.
Стаття надійшла до редакції 15.02.2010
|