как:
|[pic] |( 2.4.10) |
Следует обратить внимание на то, что в случае дискретного пространства
М (конечное число измерений) интеграл в (2.4.10) заменяется суммой.
С учетом приведенных преобразований итерация метода наискорейшего
спуска принимает вид:
|pjn = pjn-1 - ((((Fn-1)j |( 2.4.11) |
где n - номер итерации.
D. Пример применения
В качестве примера рассмотрим функцию v(r) в виде v(r)=(ci((i(r), i=1,N
, где (i(r) - множество линейно независимых базовых функций с
коэффициентами ci. Рассматривая коэффициенты ci в роли параметров
аппроксимации (ci=pi ) получим из (2.4.9) для компонентов градиента
импеданса:
|[pic] |( 2.4.12) |
В случае проводящего ОК, состоящего из N параллельных слоев с
проводимостью (j распределение электропроводности по глубине можно
представить с помощью функций Хевисайда H(z) как ((z)=( (j([ H( z-zj ) - H(
z-zj+1 ) ].
Подставляя в (2.4.12) базовые функции вида (i(z)=[H( z-zj )-H( z-zj+1
)], получим окончательное выражение:
|[pic] |( 2.4.13) |
Отметим основное преимущество такого решения. Несмотря на определенную
сложность вычислений при решении интегральных уравнений (2.4.2-2.4.8) для
расчета градиента импеданса НВТП необходимо решить только две такие задачи.
2.4.2 Отечественные методы решения
Подход, в значительной мере аналогичный работам [45-51] был предложен в
работе [41]. Из-за небольшого объема в ней уделено недостсточное внимание
вопросам практической реализации, объяснены не все обозначения и не
приведены результаты численного моделирования. В целом это значительно
снижает практическую ценность статьи. Приведем основные положения этой
работы.
Прямая задача
Пусть круговой виток радиусом а с током I находится в точке
P=Ps(r,(,z), (((-(,() вблизи немагнитного ОК, занимающего область V. Пусть
ОК обладает электрической проводимостью (=(0(((Р) являющейся произвольной
функцией координат. Требуется по N измерениям величины э.д.с. определить (
как функцию координат точек P(V. Причем i-ое измерение э.д.с. будем
проводить на i-ом измерительном круговом витке с координатами Pi=Pi(r,(,z)
i=1,N при неизменных частоте и расположении возбуждающего витка.
В общем случае напряженность электрического поля Е определяется через
векторный магнитный потенциал А, причем А = А0 + Авн, где А0 -
возбуждающий, а Авн - вносимый потенциалы.
| [pic] |(2.4.14) |
Вводя функцию Грина G(p,p0) получим
|[pic] |(2.4.15) |
При этом вносимая напряженность электрического поля
|Eвн = -j(((Aвн |(2.4.16) |
Вносимая э.д.с., наводимая в i-ом витке
|[pic] |(2.4.17) |
где функция Грина G(P,P0) имеет вид
|[pic] |(2.4.18) |
В дальнейшем рассмотрим случай, при котором V-полупространство
(r>0,\(\0 |(6.2) |
Непрерывную функцию ((х) называют штрафом, если ((х)=0 для х( Х и
((х)>0 в противном случае. Функция ((х) должна быть выбрана таким образом,
чтобы решение задачи (6.2) сходилось при ((0 к решению исходной задачи
(6.1) или, по крайней мере, стремилось к нему.
Приведем часто используемые выражения для штрафа :
|[pic] , k>0 |(6.3) |
|[pic] |(6.4) |
|[pic] |(6.5) |
Наибольшее применение находит штраф (6.3). Выражение (6.5) гарантирует
конечность метода при любом k>0.
При численной реализации метода штрафных функций возникают проблемы
выбора начального значения параметра ( и способа его изменения. Сложность
состоит в том, что выбор достаточно малого ( увеличивает вероятность
сходимости решения (6.2) к решению (6.1), а скорость сходимости градиентных
методов вычисления точек минимума (6.2), как правило, падает с убыванием
величины ( .
6.2 Релаксационные методы
Релаксационным методом называют процесс построения последовательности
точек {хk: хk ( X , (( хk+1 ) ( (( хk ) ; k=0,1... }. Основными
представителями этого класса являются методы спуска, алгоритм которых
состоит из следующих шагов :
Выбор начального приближения х0
Выбор в точке хk направления спуска -sk
Нахождение очередного приближения хk+1 = хk - (k(sk , где длина шага (k>0
Различия методов состоят в выборе либо направления спуска, либо способа
движения вдоль выбранного направления. В последнем случае обычно используют
одномерную минимизацию функции хk+1(() = хk - ((sk (при этом точность
вычисления точки минимума функции хk+1(() следует согласовывать с точностью
вычисления значений функции ((х)) или способ удвоения ((величина шага
удваивается пока выполняется условие ((хk+1) ( ((хk) ).
6.2.1 Метод условного градиента
Идея метода заключается в линеаризации нелинейной функции ((х). В этом
методе выбор направления спуска осуществляется следующим образом :
1. Линеаризируя функцию ((х) в точке хК получаем Ф(х)= (( хk ) + ( (( хk
)’ , х - хk )
2. Минимизируя линейную функцию Ф(х) на множестве Х находим хmin
3. Направление спуска получаем как -sk = хmin - хk
Таким образом итерация метода имеет вид: xk+1=xk+(k((sk+1 - xk) ,
sk+1=arg min((f(xk),x).
Основное преимущество метода проявляется в случае задания допустимого
множества с помощью линейных ограничений. В этом случае получаем задачу
линейного программирования, решаемую стандартными методами(например
симплексным).
6.2.2 Метод проекции градиента
Этот метод является аналогом метода градиентного спуска, используемого
в задачах без ограничений. Его идея состоит в проектировании точек,
найденных методом наискорейшего спуска, на допустимое множество,
определяемое ограничениями. Проекцией точки y на множество Х называется
точка P(y)(Х такая, что || P(y) - y || ( || x - y || для всех х(Х. Задача
проектирования формализуется как || x - y ||2( min, x(Х.
Выбор направления спуска осуществляется следующим образом :
1. Находим точку rk = хk - (( (’( хk )
2. Находим проекцию pk точки rk на множество Х
3. Направление спуска получаем как -sk = pk - хk
Таким образом итерация метода имеет вид: xk+1=PX[ xk - (k((f( xk ) ],
где РX(у) - ортогональная проекция точки у на множество Х.
Для отыскания направления спуска sk необходимо решить задачу
минимизации квадратичной функции || rk - х ||2 на множестве Х. В общем
случае эта задача того же порядка сложности, что и исходная, однако для
задач, допустимое множество которых имеет простую геометрическую структуру,
отыскание проекции значительно упрщается. Например, для многомерного
параллелепипида QN={x(RN : a ( x ( b }, отыскание проекции осуществляется
путем сравнения n чисел и имеет вид P(x)={ ai, xi(ai ; xi, xi([ ai,bi ] ;
bi, xi(bi }.
6.2.3 Метод случайного спуска
Метод характеризуется тем, что в качестве направления спуска sK
выбирается некоторая реализация n-мерной случайной величины S с известным
законом распределения. Об эффективности этого метода судить трудно, однако
благодаря использованию быстродействующих ЭВМ он оказывается практически
полезным.
6.3 Метод множителей Лагранжа
Идея метода состоит в отыскании седловой точки функции Лагранжа задачи
(6.1). Для нахождения решения вводится набор переменных (i , называемых
множители Лагранжа, и составляется функция Лагранжа, имеющая вид:
|[pic] |(6.6) |
Алгоритм метода состоит в следующем:
Составление функции Лагранжа
Нахождение частных производных функции Лагранжа
|[pic] |(6.7) |
3. Решение системы из n+m уравнений вида
|[pic] |(6.8) |
Решениями системы (6.8) являются точки, которые могут быть решениями
задачи.
4. Выбор точек, в которых достигается экстремум и вычисление функции
((х) в этих точках.
7. Линейное программирование
Задача линейного программирования в каноническом виде имеет вид[15,16]:
|[pic] |(7.1) |
Приведение к каноническому виду любой задачи линейного программирования
осуществляется путем введения дополнительных неотрицательных переменных, за
счет чего ограничения, имеющие вид неравенств, принимают вид эквивалентных
им равенств.
Любая задача линейного программирования может быть решена за конечное
число итераций с помощью симплексного метода[17,18]. Следует отметить, что
поскольку этот метод разработан для неотрицательных элементов xj , это
условие учитывается неявно и в систему уравнений (7.1) при численной
реализации не входит.
7.1 Алгоритм симплексного метода
1. Приведение к каноническому виду
2. Выбор начального базиса
3. Проверка оптимальности базиса
Матрицу А можно рассматривать как совокупность столбцов aj т.е.
(aj(xj=b где j=1,N. Не ограничивая общности можно считать, что базис
образуют первые m столбцов, тогда остальные можно представить в виде
ak=(aj((jk , j=1,m где (jk.- некоторые числа.
Рассмотрим коэффициенты (k=(cj((jk - ck где j=1,m и k=1,N. Заметим,
что для базовых столбцов (k ( 0. Проверка на оптимальность осуществляется
следующим образом:
| (k ( 0 , |- текущий базис оптимален |
|k=1,N | |
|[pic] |- решение не ограничено сверху |
|[pic] |- существует другой, более подходящий базис |
4. Составление нового базиса
4.1 Выбор элемента для введения в базис.
В базис вводится любой столбец, для которого (k( 0, обозначим его (p
4.2 Выбор элемента исключаемого из базиса
Из текущего базиса исключается столбец, для которого минимально
отношение bi/Aip , i=1,M обозначим его br/Arp
3 Преобразование вектора b и матрицы А по методу Жордана-Гаусса
|[pic] |[pic] |
4.4 Переход к пункту 3
8. Одномерная минимизация
Несмотря на кажущуюся простоту, для широкого класса функций решение
задачи минимизация функции одного переменного ((х) сопряжено с некоторыми
трудностями. С одной стороны, в практических задачах часто неизвестно,
является ли функция дифференцируемой. С другой стороны, задача решения
уравнения (((х)=0 может на практике оказаться весьма сложной. Ввиду этого
существенное значение приобретают методы минимизации, не требующие
вычисления производной[15].
Поскольку нас интересует приближенное определение точки минимума, то
для этого исследуют поведение функции в конечном числе точек, способами
выбора которых различаются методы одномерной минимизации.
К методам, в которых при ограничениях на количество вычислений значений
((х) достигается в определенном смысле наилучшая точность, относятся методы
Фибоначчи и золотого сечения[17,18]. Оба метода строятся по единой схеме и
различаются способом выбора параметра (. Исходными данными для них
являются: отрезок [a0,b0] содержащий точку минимума и точность определения
точки минимума (.
8.1 Алгоритм методов
I. h0 = b0 - a0 , k = 1 , ( ( (0.5,1) , h1 = ((h0 , h2 = h0 - h1 , c1 = a0
+ h2 , d2 = b0 - h2
II. Вычислить текущие значения ((ck) и ((dk) и действовать в соответствии с
ними:
| |(( ck ) ( ((|(( ck ) ( ((|
| |dk ) |dk ) |
|ak = |ak-1 |ck-1 |
|bk = |dk-1 |bk-1 |
|dk = |ck-1 | |
|ck = | |dk-1 |
|hk+2 =|hk-hk-1 |hk-hk-1 |
|dk = | |bk-hk+2 |
|ck = |ak+hk+2 | |
III. Если ( hk ( ( ) то xmin=min{ ((ck) , ((dk) } иначе k++ и переход к
шагу II
Следует отметить, что на каждом шаге кроме первого, производится только
одно вычисление значения функции ((x).
Легко показать, что для получения оптимальной последовательности
отрезков, стягивающихся к точке минимума, необходимо положить (k = Fk-1/Fk
, где F - число Фибоначчи.
8.2 Метод Фибоначчи
Решая вопрос, при каких значениях параметра ( за конечное число
итераций N мы получим отрезок минимальной длины, получим ( = (N = FN-1/FN.
Иначе говоря, для поиска минимума первоначально необходимо найти число
Фибоначчи N такое, что FN+1((b0-a0)/((FN+2.
8.3 Метод золотого сечения
В реальной ситуации начиная поиск минимума мы не знаем точного числа
требуемых итераций. Вместо вычисления ( будем выдерживать постоянное
отношение длин интервалов hk-2/hk-1 = hk-1/hk = (. При ( = ((5+1)/2 =
1.618034 получаем метод золотого сечения.
Сравнивая приведенные методы при больших значениях N можно показать,
что значение окончательного интервала неопределенности в методе золотого
сечения лишь на 17% больше чем в методе Фибоначчи.
