Министерство образования и наукиУкраины
Национальный аэрокосмическийуниверситет им. Н.Е. Жуковского
«ХАИ»
Реферат
по СМПР на тему:
«Структуризация задачпринятия решений в условиях определенности. Некорректно поставленные задачи.Регуляризирующие (робастные) алгоритмы: адаптивные, инвариантные»
Выполнил: ст. 440М гр.
Авраменко Екатерина
Проверил: Трончук
Алексей Адамович
Харьков 2008
Оглавление
Введение
1.Принятие решений в условиях определенности
1.1Определение
1.2.Классификация
1.3Определенность
1.4Методы
2.Некорректно поставленные задачи
3.Регуляризирующие алгоритмы
4.Адаптивные регуляризирующие алгоритмы
Вывод
Списокиспользованных источников
/>/>/>/> Введение
Людям приходитсяпринимать решения почти везде и почти всегда. В ходе военных действий, вполитике, при управлении предприятием, при выборе автомобиля или вариантаобмена квартиры и еще в тысячах других случаев. Занимаются люди этиминтересным, нередко захватывающим и часто небезопасным делом со времен фараонови по сей день. Поэтому достоин удивления тот факт, что люди осознали то, КАКони принимают решения совсем недавно (по историческим меркам) — вскоре послеВторой мировой войны. Оказалось, что схема процесса принятия решения не зависитот той области, в которой принимается решение. Иначе говоря, законы принятиярешений едины для всех предметных областей. В них крайне нежелательны ошибки,которые могут привести к пагубным последствиям. Но из-за ограниченныхинформационных возможностей человека ошибки всегда возможны. Поэтому естьнастоятельная необходимость применения научного подхода к обоснованию и принятию решений.
Принятие решений, наряду с прогнозированием, планированием, ситуационным анализомобстановки, исполнением решений, контролем и учетом является функциейуправления. Все функции управления направлены так или иначе на формирование илиреализацию решений, и любую функцию управления технологически можно представитьв виде последовательности каких-либо связанных общей целью решений.
Припрогнозировании и планировании принимаются решения, связанные с выбором методови средств, организацией работы, оценкой достоверности информации, выборомнаиболее достоверного варианта прогноза и наилучшего варианта плана. Такимобразом, функция принятия решений является сметодологической и технологической точек зрения более общей, чем другие функцииуправления. Для лица, принимающего решение (ЛПР),принятие решений является основной задачей, которуюон обязан исполнять в процессе управления. Поэтому знание методов, технологий исредств решений этой задачи является необходимым элементом квалификациируководителя, базой для дальнейшего управления.
В даннойработе будут рассмотрены классификация и методы для задач принятия решений,конкретизировано понятие принятия решений в условиях определенности. Рассмотреныпонятия и приведены примеры некорректно поставленной задачи, регуляризирующегоалгоритма, адаптивного алгоритма.
/>/>/>/> 1. Принятиерешений в условиях определенности
1.1 Определение
Проблемапринятия решений носит фундаментальный характер, что определяется ролью,которую играют решения в любой сфере человеческой деятельности. Исследованияэтой проблемы относятся к числу междисциплинарных, поскольку выбор способадействий — это результат комплексной увязки различных аспектов:информационного, экономического, психологического, логического,организационного, математического, правового, технического и др.
Общаятеория принятия решений, разработанная на основе математических методов иформальной логики, используется в экономике и имеет предпосылки для широкогораспространения.
С позиции данной теориипринятие решений по существу есть не что иное, как ВЫБОР. Принять решение — значит выбрать конкретный вариант действий из некоторого множества вариантов.Обычно их число конечно, а каждый вариант выбора определяет некоторый результат(экономический эффект, прибыль, выигрыш, полезность, надежность и т.д.),допускающий количественную оценку. Показатель, значение которого характеризуетпредельно достижимую эффективность по данной задаче, называется критериемоптимальности. (Ист. №4)
1.2 Классификация
Управленческие решенияцелесообразно группировать на основе классификационных признаков, приведенныхна рис. 1. (Ист. №5)
Решения, принимаемые вусловиях определенности, применяются тогда, когда естьисчерпывающая информация о проблемной ситуации. Такие решения полностьюпрограммируемы. Руководитель, сталкиваясь с различными задачами, замечает, чтонекоторые из них периодически повторяются.
Решения, принимаемые вусловиях вероятной определенности или с элементами риска,применяются с осознанием того, что имеющейся информации недостаточно или онаможет быть недостоверной. Руководитель, как правило, может предвидеть всеварианты последствий реализации такого решения. Эти решения частичнопрограммируемы. Решения, принимаемые в условиях неопределенности, когдаинформации о проблемной ситуации явно недостаточно для принятия правильногорешения, совершенно непрограммируемы. В условиях неопределенности, как правило,принимаются решения по новым и творческим задачам. (Ист. №5)
/>
Рис. 1.Классификация управленческих решений
Управленческие решениядолжны быть: эффективными, своевременными, рациональными, обоснованными иреально осуществимыми.
1.3 Определенность
Решение принимается вусловиях определенности, когда руководитель может с точностью определитьрезультат каждого альтернативного решения, возможного в данной ситуации.Сравнительно мало организационных или персональных решений принимается вусловиях определенности. Однако они все-таки имеют место. Кроме того, элементысложных крупных решений можно рассматривать как определенные. Уровеньопределенности при принятии решений зависит от внешней среды. Он увеличиваетсяпри наличии твердой правовой базы, ограничивающей количество альтернатив иснижающей уровень риска.
Как уже говорилось выше, решений, принимаемых в условиях абсолютной определенности, в реальной жизни быть не может. Однако существуют ситуации, когда решение принимается в условиях почти полной определенности. Например, решение о вложении нераспределенной прибыли в ценные бумаги государства. В данном случае менеджер точно знает размер вкладываемой суммы, может выбрать сроки вложения, рассчитать доходность и может точно подсчитать планируемую прибыль от данного вложения и сроки ее получения. Государство может не выполнить свои обязательства только при возникновении чрезвычайных обстоятельств, вероятность возникновения которых очень мала. (Ист. №6)
1.4 Методы
Решение может бытьформальным и творческим. Принято считать, что если преобразование информациивыполняется с помощью математических моделей, то выработанное решение считаетсяформальным, если решение появляется в результате скрытой работы интеллекта человека,принимающего решение, то оно — творческое.
Такое деление вдостаточной степени условно, поскольку чисто формального или чисто творческогорешения не существует. Если решение вырабатывается с помощью математическоймодели, то знания и опыт человека (элементы творчества) используются при еёсоздании, а интуиция (тоже момент творчества) – в момент, когда он задаёт тоили иное значение параметра исходной информации или выбирает из множестваальтернативных вариантов, полученных с помощью математической модели, один вкачестве решения на управление. Если основным инструментом выработки решенияявляется интеллект человека, то формальные методы, носителем которыхпрактически является вся наука, скрыто присутствуют в его знаниях и опыте.
Формализуемые решенияпринимаются на основе соответствующих математических методов (алгоритмов).Математическая модель задачи оптимизации формализуемого решения включаетследующие элементы:
1. заданнуюоптимизируемую целевую функцию (критерий управляемости): Ф=F(x1,x2,:,xn),где xj (j=1,2,:,n) — параметры, учитываемые при принятии решения(отражающие ресурсы принятия решений);
2. условия,отражающие ограниченность ресурсов и действий ЛПР при принятии решений: gi(xj)
Непременным требованиемдля решения задачи оптимизации является условие n>m.
В зависимости откритерия эффективности, стратегий и факторов управления выбирается тот или инойметод (алгоритм) оптимизации.
Основными являютсяследующие классы методов:
1. методылинейного и динамического программирования (принятия решения об оптимальномраспределении ресурсов);
2. методытеории массового обслуживания (принятие решения в системе со случайнымхарактером поступления и обслуживания заявок на ресурсы);
3. методыимитационного моделирования (принятие решения путем проигрывания различныхситуаций, анализа откликов системы на различные наборы задаваемых ресурсов);
4. методытеории игр (принятие решений с помощью определения стратегии в тех или иныхсостязательных задачах);
5. методытеории расписаний (принятие решений с помощью разработки календарных расписанийвыполнения работ и использования ресурсов);
6. методысетевого планирования и управления (принятие решений с помощью оценки иперераспределения ресурсов при выполнении проектов, изображаемых сетевымиграфиками);
7. методымногокритериальной (векторной) оптимизации (принятие решений при условиисуществования многих критериев оптимальности решения)
и другие методы. (Ист.№9)
/>/>/>/> 2. Некорректнопоставленные задачи
Вкачестве основного объекта рассматривается операторное уравнение: Az =u,где A — линейный оператор, действующий из гильбертова пространства Z вгильбертово пространство U. Требуется найти решение операторногоуравнения z, соответствующее заданной неоднородности (или правой частиуравнения) u.
Такоеуравнение является типичной математической моделью для многих физических, такназываемых обратных, задач, если предполагать, что искомые физическиехарактеристики z не могут быть непосредственно измерены, а в результатеэксперимента могут быть получены только данные u, связанные с z спомощью оператора A.
Французскимматематиком Ж. Адамаром были сформулированы следующие условия корректностипостановки математических задач, которые мы рассмотрим на примере записанногооператорного уравнения. Задача решения операторного уравнения называетсякорректно поставленной (по Адамару), если выполнены следующие три условия(условия корректности):
1)задача имеет решение при любых допустимых исходных данных (решение существует ∀u∈U);
2)каждым исходным данным u соответствует только одно решение (решениеединственно);
3)решение устойчиво (если u n →u,/> ,Az = u ,то z n →z).
Смысл первогоусловия заключается в том, что среди исходных данных нет противоречащих другдругу условий, что исключало бы возможность решения задачи.
Второеусловие означает, что исходных данных достаточно для однозначной определённостирешения задачи. Эти два условия обычно называют условиями математическойопределённости задачи. Условие 2) обеспечивается тогда и только тогда, когдаоператор A является взаимно однозначным (инъективным). Условия 1) и 2)означают, что существует обратный оператор /> , причем егообласть определения D(/>) (или множествозначений оператора A, R(A)) совпадает с U.
Условие3) означает, что обратный оператор /> являетсянепрерывным, т.е. “малым” изменениям правой части u соответствуют“малые” изменения решения z. Третье условие обычно трактуется какфизическая детерминированность задачи. Это объясняется тем, что исходные данныефизической задачи, как правило, задаются с некоторой погрешностью; принарушении же третьего условия как угодно малые возмущения исходных данных могутвызывать большие отклонения в решении.
Задачи,не удовлетворяющие хотя бы одному условию корректности, называютсянекорректными задачами (или некорректно поставленными). Более того, Ж. Адамар считал,что только корректные задачи должны рассматриваться при решении практическихзадач. Однако хорошо известны примеры некорректно поставленных задач, кизучению и численному решению которых приходится прибегать при рассмотрениимногочисленных прикладных задач. Нужно отметить, что устойчивость инеустойчивость решения связаны с тем, как определяется пространство решений Z.Выбор пространства решений (в том числе и нормы в нем) обычно определяетсятребованиями прикладной задачи. Задачи могут быть некорректно поставленными приодном выборе нормы и корректно поставленными при другом.
Многочисленныеобратные (в том числе и некорректные) задачи можно найти в различных областяхфизики. Так, астрофизик не может активно воздействовать на процессы,происходящие на далеких звездах и галактиках, ему приходится делать заключенияо физических характеристиках весьма удаленных объектов по их косвеннымпроявлениям, доступным измерениям на Земле или вблизи Земли (на космическихстанциях). Прекрасные примеры некорректных задач можно найти в медицине, преждевсего, нужно отметить вычислительную (или компьютерную) томографию. Хорошоизвестны приложения некорректных задач в геофизике (на самом деле, легче идешевле судить о том, что делается под поверхностью Земли, решая обратныезадачи, чем заниматься бурением глубоких скважин), радиоастрономии,спектроскопии, ядерной физике и т.д., и т.п.
Хорошоизвестным примером некорректно поставленной задачи является интегральное уравнениеФредгольма 1-го рода. Пусть оператор A имеет вид:
/>
Пустьядро интегрального оператора K(x,s)-функция, непрерывная по совокупности аргументов x ∈[c,d],s ∈[a,b],а решение z(s)-непрерывная на отрезке [a,b]функция.Тем самым, можно рассматривать оператор A как действующий в следующихпространствах: A :C[a,b]→C[c,d].(Пространство C[a,b]состоитиз функций, непрерывных на отрезке [a,b].Норма z ∈C[a,b]определяетсякак />). Покажем, чтов этом случае задача решения интегрального уравнения является некорректнопоставленной. Для этого нужно проверить условия корректности постановки задачи:
1) Существованиерешения для любой непрерывной на [c,d]функцииu(x). На самом же деле, это не так: существует бесконечно много непрерывныхфункций, для которых решения нет.
2)Единственность решения. Это условие выполняется в том и только в том случае,если ядро интегрального оператора замкнуто.
Первыедва условия корректности эквивалентны условию существования обратного оператора/> с областьюопределения D(/>)=C[c,d].Если ядро интегрального оператора замкнуто, то обратный оператор существует,однако область его определения не совпадает с C[c,d].
3) Устойчивостьрешения. Это означает, что для любой последовательности /> последовательностьz n →/>. Устойчивостьэквивалентна непрерывности обратногооператора /> при условии,что обратный оператор существует. В данном случае это нетак,что видно из следующего примера. Пусть последовательность непрерывных функций /> ,n=1, 2, …, такая, что /> на промежутке /> и обращается внуль вне данного интервала, max| z (s) |=1, s∈[a,b], а последовательность чисел d → 0+0.
4) Такаяфункция может быть выбрана, например, кусочно-линейной. Тогда для любого x ∈[c,d]
/>
при/>
Последовательностьфункций /> равномерно,т.е. по норме C[c,d], сходится к /> =0.
Хотярешение уравнения /> вэтом случае /> =0, последовательность /> не стремится к /> ,так как/>.
Интегральныйоператор A является вполне непрерывным при действии из /> в
/>, при действиииз C[a,b] в /> и при действиииз C[a,b] в C[c,d]. (Пространство
/> состоит изфункций, интегрируемых с квадратом на отрезке [a,b].Норма z∈/> определяетсякак /> ).Это означает, что любую ограниченную последовательностьэтот оператор преобразует в компактную. Компактная последовательность поопределениюобладает тем свойством, что из любой ее подпоследовательности можно выделитьсходящуюся.Легко указать последовательность /> ,/>, из которойнельзя выделить сходящуюся в C[a,b] подпоследовательность.Например,
/>
Нормывсех членов этой последовательности равны 1 в /> , но из любой подпоследовательностиэтой последовательности нельзя выделить сходящуюся, поскольку /> . Очевидно, чтоэта последовательность состоит из непрерывных на [a,b] функций иравномерно (по норме C[a,b]) ограничена, но из этойпоследовательности нельзя выделить сходящуюся в C[a,b]подпоследовательность (тогда она сходилась бы и в />, поскольку изравномерной сходимости следует сходимость в среднем). Если предположить, чтооператор /> являетсянепрерывным, то легко прийти к противоречию. Для существования обратногооператора достаточно потребовать, чтобы прямой оператор A былинъективным. Очевидно, что, если оператор B: C[c,d]→C[a,b]непрерывный, а оператор A вполне непрерывный, то BA :C[a,b]→C[a,b]- тоже вполне непрерывный оператор. Но тогда, поскольку для любого n />, топоследовательность /> компактна,что неверно. Оператор, обратный к вполне непрерывному оператору, не может бытьнепрерывным. Аналогичное доказательство может быть проведено для любыхбесконечномерных банаховых (т.е. полных нормированных) пространств.
Посколькузадача решения интегрального уравнения Фредгольма первого рода в указанныхпространствах некорректно поставлена, то даже при очень малых ошибках в заданииu(x) решение может либо отсутствовать, либо как угодно сильноотличаться от искомого точного решения.
Итак,вполне непрерывный инъективный оператор обладает обратным оператором, которыйне является непрерывным (ограниченным). Более того, при действии в бесконечномерныхбанаховых пространствах множество значений вполне непрерывного оператора не являетсязамкнутым. Поэтому как угодно близко к неоднородности u(x), для которойрешение операторного уравнения существует, найдется неоднородность, для которойрешение отсутствует.
Некорректностьпостановки математической задачи может быть связана с ошибкой в заданииоператора. Простейший пример дает задача отыскания нормального псевдорешениясистемы линейных алгебраических уравнений и возникающая при этомнеустойчивость, связанная с ошибками задания матрицы.
Пустьдана система линейных алгебраических уравнений (СЛАУ):
/>
Системаможет и не иметь решений. Гаусс и Лежандр в начале XIX века ввели метод наименьшихквадратов, а именно, вместо решения СЛАУ предложили минимизировать квадратичныйфункционал (невязку):
/>
/> - сопряженная(транспонированная) матрица. Поскольку матрица /> неотрицательно
определена,то Ф(x)- выпуклый функционал. Для выпуклого функционала задачаотыскания /> эквивалентнаотысканию стационарной точки, т.е. решения уравнения Ф'(x) =0. Легко видеть, что Ф' (x) = 2⋅(/>Ax −/>b),Ф''(x) = 2 ⋅/>A ≥0.
Изравенства градиента нулю получается система линейных алгебраических уравнений сквадратной неотрицательно определенной матрицей (система нормальных уравнений):
/>
Вконечномерном случае легко доказать, что для любого вектора b системанормальных
уравненийвсегда имеет решение (для исходного же уравнения это не обязательно), котороеназывается псевдорешением системы Ax = b.Псевдорешение может быть неединственным (если определитель det(/>A)=0;если же det(/>A)≠0,то псевдорешение единственно). Множество псевдорешений образует аффинное (илилинейное) подпространство и является выпуклым и замкнутым.
Еслиже система Ax =b имеетрешение, то оно совпадает с решением системы /> Ax =/>b .В этом случае minФ(x) =μ=0.Если же minФ(x) =μ>0,система Ax = b неимеет решений, но, какуже указывалось выше, имеет псевдорешение(возможно, неединственное). Число μ обычноназывается мерой несовместности системы Ax =b.
Определение.Нормальноепсевдорешение /> системы Ax =b–это псевдорешение с
минимальнойнормой, что является решением задачи отыскания минимума />.
Можнопривести много др. примеров классических математических задач, являющихсянекорректными при совершенно естественном выборе понятий меры точности как дляисходных данных задачи, так и для возможных решений: решение систем линейныхалгебраических уравнений с определителем, равным нулю; задача оптимальногопланирования; решение интегральных уравнений 1-го рода; задача аналитическогопродолжения; суммирование рядов Фурье; большое число краевых задач дляуравнении с частными производными. (Ист. №10)
/>/>/>/>3. Регуляризирующиеалгоритмы
Пустьдано операторное уравнение: Az = u,где A — линейный оператор, действующий из нормированного пространства Zв нормированное пространство U. В 1963 г. А.Н.Тихонов дал знаменитоеопределение регуляризирующего алгоритма (РА), которое лежит в основесовременной теории некорректно поставленных задач.
Определение.Регуляризирующим алгоритмом (регуляризирующим оператором) /> называетсяоператор, обладающий двумя следующими свойствами:
1)/> определен длялюбых δ> 0, /> ∈U,и отображает (0,+ ∝)×UвZ;
2)для любого z ∈ Zидля любого /> ∈Uтакого,что Az = u ,/>
/>.
Задачарешения уравнения первого рода называется регуляризируемой, если существуетхотя бы один регуляризирующий алгоритм. Непосредственно из определения следует,что если существует хотя бы один РА, то их существует бесконечно много.
Внастоящее время все математические задачи можно разделить на следующие классы:
1)корректно поставленные задачи;
2)некорректно поставленные регуляризируемые задачи;
3)некорректно поставленные нерегуляризируемые задачи.
Понятно,что корректно поставленные задачи являются регуляризируемыми, посколькуможноположить /> . Отметим, чтознание δ> 0в этом случае необязательно.
Далеконе все некорректно поставленные задачи можно регуляризировать, причем это частозависит от выбора пространств Z, U. Российский математикЛ.Д.Менихес построил пример интегрального оператора с непрерывным замкнутымядром, действующего из пространства C[0,1] в />, обратнаязадача для которого (т.е. решение интегрального уравнения Фредгольма 1-го рода)является нерегуляризируемой. Это связано со свойствами пространства C[0,1].Ниже будет показано, что если пространство Z гильбертово, а оператор Aограниченный и инъективный, то задача решения операторного уравненияпервого рода является регуляризируемой. Этот результат справедлив и длянекоторых банаховых пространств, но не для всех. В частности, пространство C[0,1]к таким банаховым пространствам не относится.
Можнодать эквивалентное определение регуляризирующего алгоритма и регуляризируемостиоператорного уравнения. Пусть задан оператор (отображение) />, причем /> определен длялюбых δ> 0,/> ∈U,иотображает (0,+ ∝) ×UвZ. Погрешность решения операторного уравнения в точке z ∈Zспомощью оператора /> при условии,что правая часть u задана с погрешностью δ >0,определяется как
/>
Оператор/> называетсярегуляризирующим оператором, если для любого z ∈Z/> . Легковидеть, что данное определение эквивалентно данному выше.
Аналогичноможно дать определение регуляризирующего алгоритма для задачи вычислениязначений оператора (см. конец предыдущего параграфа), т.е. для задачивычисления значений отображения G : D(G) →Y,D(G) ⊆ Xприусловии, что аргумент задан с погрешностью (X, Y – метрическиеили нормированные пространства). Разумеется, задача решения операторногоуравнения при условии, что A – инъективный оператор, можетрассматриваться как задача вычисления значений оператора />.
Огромноезначение имеет ответ на следующий очень важный вопрос, можно ли решить некорректнуюзадачу, т.е. построить регуляризирующий алгоритм, не зная погрешность δЕслизадача корректна, то устойчивый метод, очевидно, можно построить и без знания δ.
Так,в случае решения операторного уравнения />. В случаенекорректных задач это невозможно. Приведенная ниже теорема принадлежитА.Б.Бакушинскому и была им доказана для задачи вычисления значений оператора.Аналогичная теорема имеет место и для решения операторного уравнения.
Теорема.Если для вычислений значений оператора G на множестве D(G)⊆Xсуществуетрегуляризирующий оператор, не зависящий от δ (явно),то существует продолжение G на X , которое непрерывно на D(G)⊆X.
Итак,построение регуляризирующих алгоритмов, не зависящих явно от погрешности,
возможнотолько для задач, корректных на своей области определения.
Следующимсвойством некорректно поставленных задач является невозможность оценить погрешностьрешения, даже если известна погрешность задания правой части операторногоуравнения или погрешность задания аргумента в задаче вычисления значенийоператора. Этот принципиально важный результат был также впервые доказанА.Б.Бакушинским для решения операторного уравнения.
Теорема.Пусть /> длялюбого z ∈ D⊆Z.Тогда сужение обратного оператора на множество AD: />непрерывно на AD.Таким образом, равномерная по z оценка погрешности решения операторногоуравнения на множестве D ⊆Zвозможнатолько в том случае, когда обратный оператор непрерывен на AD. Такимобразом, равномерная по z оценка погрешности решения операторногоуравнения на множестве D ⊆Zвозможнатолько в том случае, когда обратный оператор непрерывен на AD. Даннаятеорема справедлива и для нелинейных операторных уравнений, причем вметрических пространствах.
Изопределения регуляризирующего алгоритма легко следует, что, если есть хотя быодин регуляризирующий алгоритм, то их может быть сколько угодно. Выбрать жетот, который дает наименьшую ошибку, или сравнивать алгоритмы, сравнивая ошибкиполученных приближенных решений, при решении некорректных задач, невозможно приотсутствии априорной информации, которая фактически преобразует такие задачи вкорректные.
Регуляризирующиеалгоритмы для операторных уравнений в бесконечномерных банаховых пространствахнельзя сравнивать и по скорости сходимости приближенного решения к точному пристремлении погрешности входных данных к нулю. Этот важный результат принадлежитВ.А.Винокурову. (Ист. №1)/>/>/>/>4. Адаптивныерегуляризирующие алгоритмы
1. ПустьZ,U – гильбертовы пространства, а A – линейный ограниченный оператор,действующий из Z в U. Рассмотрим операторное уравнение
/>
Безущерба для общности будем считать, что ||A|| уравнение (1)имеет нормальное псевдорешение /> . Будем решатьзадачу его устойчивого нахождения по приближенным данным уравнения (1) /> , пологаяоператор А заданным точно. Таким образом, требуется по данным /> найти такойэлемент />, который сильносходиться в Z к /> при /> .
2. Этазадача может быть решена многими методами (регуляризирующими алгоритмами).Например, для ее решения можно использовать метод невязки (в обобщенной формедля решения несовместных уравнений). В этом методе приближение /> к /> ищется какрешение экстремальной задачи
/>.
Здесь/> - оценка мерынесовместности
/> решаемогооператорного уравнения. Известно, что без привлечения дополнительной информацииоб искомом решении /> или о точныхданных задачи (/>) метод невязкине может обеспечить точность приближенного решения лучше, чем />. Аналогичнаяситуация складывается и при использовании метода регуляризации А. Н. Тихонова,в котором наилучшая возможная точность есть />, как бы нивыбирался параметр регуляризации. Это явление обычно называют «насыщениемточности» регуляризирующего алгоритма (РА). Его можно избежать, если учесть вРА априорную информацию о свойствах точного решения. Например, если известно,что />, где />, то, используявеличину p, можно построить РА, которые дают приближение с порядкомточности />, оптимальным наклассе задач (1) с решениями указанного вида.
Сдругой стороны, можно, не зная величины р, но используя оценку />, построить РА,которые позволяют устойчиво определять число р и получать приближение к /> с оптимальнымпорядком точности для произвольного р>0. Алгоритмы такого родапредлагаются в данной заметке.
3. Сформулируемосновные положения. Пусть известно, что нормальное псевдорешение /> задачи (1)истокообразно представимо с помощью степени оператора />. Посколькутакое представление не единственно, будем иметь ввиду, что
/>
гдер>0 – максимально возможное число. В общем случае число р полагаетсянеизвестным, но при этом считается, что дана величина r.
Нижебудет использована величина /> - устойчиваяоценка меры несовместимости /> уравнения (1),удовлетворяющая требованиям: />
/>.
Вкачестве /> можно выбрать,например, упомянутое выше число />.
4. Методикупостроения алгоритмов рассмотрим на примере специализированного метода невязки.Предлагаемый РА основан на решении экстремальной задачи: при заданном параметре/> найти элемент /> такой, что
/>
(C=const> 1). Алгоритм состоит из двух шагов:
1) Найтичисло
/>
2) Вычислитьпри /> решение /> задачи (3) иприменять элемент /> в качествеприближения к />.
Экстремальныезадачи (3), (4) обладают важными свойствами.
Теорема1. Пустьвыполнено (2). Тогда задача (3) однозначно разрешима при всяком /> Для каждого />, найдется такоечисло />, что при любом />, для решениязадачи (3) справедлива оценка: />
Теорема2. Есливыполнено (2), то решение задачи (4) конечно, и при каждом />, для него вернаоценка
/>.
Теорема3.Если />, то для решения/> задачи (3) при /> выполненонеравенство />.
Сходимостьприближенных решений устанавливает
Теорема4.Если выполнено условие (2), то /> при /> и обеспеченысильные сходимости в Z:
/>.При этом />.
Введеммножество />. Ясно, что />. Тогда изприведенной в теореме 4 оценки и из теории оценивания погрешности приближенныхрешений некорректных задач на множествах типа /> вытекает
Теорема5.При выполнении условий (2) метод (3), (4) гарантирует при любом р>0оптимальный порядок точности приближенного решения для задач (1), у которых />.
Рассмотримслучай, когда оператор А – вполне непрерывный. Тогда множество /> - образ слабогокомпакта в Z – является сильным компактом. Это следует из того, чтооператор /> также будетвполне непрерывным. По этой причине задача решения уравнения (1) приобретаетинтересные свойства. На основе этих свойств могут быть построены регуляризирующиеалгоритмы, допускающие апостериорную оценку погрешности решения.
Отметимтеперь следующий тривиальный результат.
Теорема6.Если в дополнение к условиям теоремы 5 известны, что оператор Анормально разрешим, то алгоритм (3), (4) при любом р > 0 даетточность />.
5. Изтеорем 5,6 следует, что алгоритм (3), (4), не используя данных о степени р истокообразнойпредставимости элемента />, в процессерешения задачи сам «настраивается» на нужную величину р. В связи с этим дадим
Определение.Регуляризирующий алгоритм называется адаптивным для задач (1) с решениями изнекоторого семейства множеств {/>}, зависящих отпараметра р, если: 1) он не использует явно величину р,определяемую включением />; 2) он оптималенпо порядку точности для всякого /> независимо отдопустимого параметра р.
Примеромадаптивного РА служит алгоритм (3), (4). Имеются и другие адаптивные РА, длякоторых справедливы такие же результаты, как в теоремах 4-6. К числу таких РАотносятся специализированный метод регуляризации А.Н. Тихонова, эквивалентныйметоду (3), (4), специализированный метод квазирешений, получаемый из обычногометода квазирешений [5] по схеме, которая использована в методе (3), (4). Всеэти адаптивные алгоритмы были программно реализованы в системе MATLAB ипоказали свою высокую эффективность в численных эксперементах.
6. Остановимсяособо на случае, когда при выполнении условий (2) степень истокопредсавимости рточного решения задачи (1) известна. Тогда нет необходимости использоватьвеличину r. В качестве приближения к /> в этом случаеможно взять элемент /> - решениезадачи (3) при />
Справедлива
Теорема7. Гарантированысильные сходимости: />. Приближение /> имеетоптимальный порядок точности />. Еслиоператор А нормально разрешим, то при всяком р > 0 вернаоценка: />. (Ист. №7)
Кромеспециализированного метода невязки, адаптивными являются также и некоторыедругие регуляризующие алгоритмы. Сформулируем и кратко обсудим важнейшие изних.
Специализированныйметод регуляризации А. Н. Тихонова.Оноснован на решении следующей параметрической задачи: при фиксированном β> 0 и при заданном параметре α>0 найти элемент />, такойчто
/> (5.1)
Алгоритмэтого метода состоит из таких шагов: 1) выбор параметра регуляризации α(δ,β)>0для каждого β > 0 по (обобщенному) принципу невязки, то естькак решение уравнения
/>(5.2)
2)использованиеэлементов />, получаемыхв результате решения задачи (5.1) с
/>, длянахождения числа /> поправилу
/>
3)принятие в качестве приближения к /> элемента /> Имеетсятесная связь метода регуляризации с выбором параметра регуляризациипо(обобщенному) принципу невязки и метода невязки.
Теорема8.Элемент />, вычисляемый вшагах 1,2 алгоритма специализированного метода регуляризации, по крайней мере придостаточно малых δ совпадает с элементом /> , полученным вспециализированном методе невязки. Число />, определяемое этимиалгоритмами, — одно и то же при таких δ.
Доказательство. Существование единственного решения задачи (5.1) следует из общей теорииметода регуляризации линейных некорректных задач в гильбертовых пространствах.Существование и единственность параметра регуляризации />, выбираемогоиз условия (5.2), при каждом фиксированном βвытекает изрезультатов работ. Установлена эквивалентность принципа и метода невязки прирешении линейных операторных уравнений в гильбертовых пространствах в случае,если /> и δ достаточномало. Поэтому /> прикаждом /> >0. Но тогда задача нахождения величины /> оказываетсяодной и той же для обоих специализированных алгоритмов и поэтому имеет одно ито же решение.
Всилу установленной в теореме 4.1 эквивалентности алгоритмов специализированногометода регуляризации и специализированного метода невязки для первого из нихсправедливы те же результаты о сходимости и оптимальности порядка точностиприближений, что и для второго. Это можно суммировать так.
Теорема9.Пусть выполнены условия(2).Тогда для величин />, /> и />, полученных поспециализированному методу регуляризации, гарантируются сходимости при />.
Этотметод оптимален по порядку точности при всяких /> и при каждом p> 0. Он обеспечивает неулучшаемый порядок точности на всем классе />, каково бы нибыло p > 0, причем гарантированная верхняя оценка точности есть /> .
Теорема9 обосновывает адаптивность алгоритма специализированного метода регуляризации.
Специализированныйметод квазирешений.Он базируется нарешении экстремальной задачи: при фиксированном числе β > 0найти элемент /> , длякоторого
/> (6.1)
Взадаче (6.1) минимизируется непрерывный выпуклый (квадратичный) функционал назамкнутом, выпуклом, ограниченном множестве гильбертова пространства. Известно,что такая задача разрешима. Будем использовать далее произвольное ее решение /> при каждомрассматриваемом β > 0. Алгоритм специализированного методаквазирешений состоит из следующих шагов: 1) найти число
/> (6.2)
здесьчисловое множество /> определяетсятак:
/> (6.3)
2)решить при /> = /> задачу(6.1) и по ее решению /> найтиприближение
/>.
Множество/> из задачи (6.2)не пусто по крайней мере для «малых δ»: 0 δ Действительнопри 0 δ ипри/> справедливовключение />. Изнего и из задачи (6.1) с учетомоценки ||/>||/> для такихδ и βполучим:
/>
иэто значит, что />.
Конечностьвеличины /> устанавливается,причем для этого /> верна та жеоценка, что и в замечании 2. Из (6.1)-(6.3) следуют неравенства
/>
Используяих можно получить сходимости /> при/>. Из сказанногоясно, что для приближенных решений задачи (1), которые находятся поспециализированному методу квазирешений, верны результаты теоремы 9. Поэтомуданный алгоритм является адаптивным. (Ист.№8)
/>/>/>/> Вывод
Решение – это выбор альтернативы. Принятие решений – связующий процесс, необходимый для выполнения любой управленческой функции. Лицо, принимающее решение своими решениями может повлиять на судьбы многих людей и организаций.
В зависимости от уровня сложности задач, среда принятия решений варьируется в зависимости от степени риска. Условия определенности существуют, когда руководитель точно знает результат, который будет иметь каждый выбор.
Методы приближённого решения некорректно поставленных задач и их применений к решению обратных задач имеют важное значение для автоматизации обработки наблюдений и для решения проблем управления. Имеется много работ (особенно советских математиков), посвященные этим методам.
Существоваломнение, что некорректные задачи не могут встречаться при решении физических итехнических задач и что для некорректных задач невозможно построениеприближённого решения в случае отсутствия устойчивости. Расширение средствавтоматизации при получении экспериментальных данных привело к большомуувеличению объёма таких данных; необходимость установления по ним информации оестественнонаучных объектах потребовала рассмотрения некорректных задач.Развитие электронной вычислительной техники и применение её к решениюматематических задач изменило точку зрения на возможность построенияприближённых решений некорректно поставленных задач.
Изопределения регуляризирующего алгоритма легко следует, что, если есть хотя быодин регуляризирующий алгоритм, то их может быть сколько угодно. Выбрать жетот, который дает наименьшую ошибку, или сравнивать алгоритмы, сравнивая ошибкиполученных приближенных решений, при решении некорректных задач, невозможно приотсутствии априорной информации, которая фактически преобразует такие задачи вкорректные.
Кчислу адаптивных регуляризирующих алгоритмов относятся специализированный методрегуляризации А.Н. Тихонова, специализированный метод квазирешений, получаемыйиз обычного метода квазирешений по определенной схеме. Все эти адаптивныеалгоритмы были программно реализованы в системе MATLAB и показали свою высокуюэффективность в численных эксперементах.
/> Списокиспользованных источников
1. БакушинскийА. Б., Гончарский А.В. Некорректные задачи. Численные методы и приложения. –М.: Изд-во Моск. ун-та, 1989. – 199 с./>/>/>2. Большая советская энциклопедия. — Статья34622. Корректные и некорректные задачи С.1154 [Электронный ресурс] www.diclib.com/cgibin/d1.cgi?l=ru&base=bse&page=showid&id=34622
3. ГимадиЭ.Х. О некоторых математических моделях и методах планирования крупномасштабныхпроектов / Э.Х. Гимади //Модели и методы оптимизации. Труды Институтаматематики. — Новосибирск.: Наука. Сиб. Отд–ние. — 1988. — С. 89–115/>/>/>4. Горский П. Введение в прикладнуюдисциплину «поддержка принятия решений» С.1-5 [Электронный ресурс] www.devbusiness.ru/development/dms/dms_intro.htm/>/>/>5. Грищенко О.В. Управленческий учет/ О.В.Грищенко// Понятие об управленческих решениях и их классификация //Конспект лекций. — Таганрог.: ТТИ ЮФУ,2007. – 69 с. [Электронный ресурс] www.aup.ru/books/m166/6_1.htm
6. КазиевВ.М. Введение в анализ, синтез и моделирование систем. / В.М. Казиев // Лекция13: Основы принятия решений и ситуационного моделирования. – М.: Интернетунивер. – 2006. — С.49-53 [Электронный ресурс] www.intuit.ru/department/expert/intsys/13/4.html
7. ЛеоновА.С., Ягола А.Г. Адаптивные регулизирующие алгоритмы для решения некоректныхзадач / М.: Вестник Московского университета. — 1998. — No. 2 (март-апрель). — С. 62-63 [Электронный ресурс]
http://www.phys.msu.ru/upload/iblock/a84/98-2-62.pdf
8. ЛеоновА.С., Ягола А.Г. Оптимальные методы решения некорректных задач с истокообразнопредставимыми решениями / М.: Фундамент. и прикл. матем. — 1998том4,выпуск3. – С. 1029–1046 [Электронный ресурс] www.mathnet.ru/links/def37868bce5b5f5d14bfa300b7b6912/fpm_340_card_rus.pdf
9. ПланкеттЛ., Выработка и принятие управленческих решений, М.: Наука, 1984 г. – 146с.
10. ТихоновА.Н. О решении некорректно поставленных задач и методе регуляризации//ДокладыАН СССР. – 1963. – 151. – №3. – С.501-504.