Понятие корректно и некорректно поставленных задач.

Понятие корректно и некорректно поставленных задач.

При приближенном решении математических задач или прикладных задач весьма существенным является вопрос о том, корректна ли решаемая задача. Большинство некорректных задач может быть приведено к уравнению 1 рода, имеющему вид:

(1.1)

в котором по заданному, не обязательно линейному оператору А, действующему из пространства X в пространство Y и по заданному элементу требуется определить решение х в пространстве Х.

Определение. Задача определения решения x=R(y) из пространства Х по исходным данным называется устойчивой на пространствах Х и У, если для любого числа можно указать такое число , что неравенства следует, что где х ₁= Ry ₁, x₂=Ry₂, x₁,x₂ X, y₁,y₂ Y.

Определение. Следуя Ж. Адамару, задачу отыскания из (1.1) называют корректной (корректно поставленной), если при любой фиксированной правой части у=у₀ из Y ее решение:

а) существует в пространстве Х; б) единственно в Х; в) устойчиво в Х.

Если хотя бы одно из условий не выполняется, то задачу называют некорректной (некорректно поставленной).

Определение. Назовем задачу (1.1) корректной по Тихонову на множестве а само множество М – ее множеством корректности, если:

а) Точное решение задачи существует в классе М, б) принадлежащее множеству М решение задачи единственно для любой правой части у из множества , в) принадлежащие множеству М решение задачи устойчиво относительно любой правой части у из множества N.

Сходимость метода простой итерации в случае единственного решения

Постановка задачи

В действительном гильбертовом пространстве Н решается уравнение 1 рода

Ах = у, (1)

где А - ограниченный, положительный, самосопряжённый оператор, для которого нуль не является собственным значением. Причём нуль принад­лежит спектру оператора А, т.е. задача некорректна. Предполагается суще­ствование единственного решения х при точной правой части у. Для его отыскания предлагается итеративный метод

(2)

Однако на практике часто правая часть у уравнения (3.1) бывает неизвест­ной, а вместо у известно приближение , тогда метод (3.2) примет вид:

(3)

Если раскрыть скобки во втором слагаемом в (3.2) и (3.3), то исчезает, следовательно, вычислять и не придётся.

Как нетрудно видеть, метод (3.3) обобщает метод простой итерации, т.е.

Последний получается из (3) при к = 1.

Сходимость при точной правой части

Теорема 1. Итеративный процесс (2) при условии (4) сходится.

Доказательство.

(*)

Рассмотрим процесс (2) при n=0 т.к. то следовательно при n=1 в формула (*) верна. Предположим что формула верна при n=p, (**) и рассмотрим её при n=p+1. Подставим (**) в формулу (2). Так как уравнение (1) имеет по предположению единственное точное решение, то следовательно,

Воспользовавшись интегральным представлением самосопряженного опе­ратора

( - соответствующая спектральная функция, ), получим .

Разобьём полученный интеграл на два интеграла

Рассмотрим 1ый интеграл. При условии (4) величина

Тогда . Рассмотрим 2ой интеграл. Здесь , .

так как сильно стремится к нулю при в силу свойств спектральной функции. Следовательно, , , т.е. итеративный процесс (2) сходится, ч.т. д.

Доказательство.

Будем считать и рассмотрим разность Как показано ранее, . Воспользовавшись интегральным представлением самосопряжённого оператора А, получим и, как показано ранее то для сходимости метода (3) достаточно, чтобы ч.т. д.

Оценка скорости сходимости

Теорема 3. Если точное решение х уравнения (1) истокопредставимо, то при
условии для метода (3) справедлива оценка погрешности

Погрешность в счёте

Теорема 4. Если точное решение х уравнения (1) истокопредставимо, то при условии оптимальная оценка погрешности для метода (3) имеет вид и достигается при

Постановка задачи

В действительном гильбертовом пространстве Н решается уравнение 1 рода Ах = у, (1)

где А - ограниченный, положительный, самосопряжённый оператор, для которого нуль не является собственным значением. Причём нуль принад­лежит спектру оператора А, т.е. задача некорректна. Предполагается суще­ствование единственного решения х при точной правой части у. Для его отыскания предлагается итеративный метод (2)

Однако на практике часто правая часть у уравнения (1) бывает неизвест­ной, а вместо у известно приближение , тогда метод (2) примет вид:

(3)

Если раскрыть скобки во втором слагаемом в (2) и (3), то исчезает, следовательно, вычислять и не придётся.

Решение задачи

Для решения Ax = y используется метод (3). Все результаты полу­чены в предположении, что точное решение уравнения (1) истокопредставимо, т.е. . Однако, поскольку сведения об элементе и степени истокопредставимости s имеются не всегда, то трудно определить число итераций п, обеспечивающих схо­димость метода (3). Тем не менее этот метод можно сделать вполне эф­фективным, если воспользоваться следующим правилом останова по не­вязке.

Определим момент т останова итерационного процесса (3) усло­вии

(4)

Предполагаем, что при начальном приближении невязка достаточно велика, больше уровня останова ε, т.е.

Покажем, что правило останова по невязке применимо к методу (3). Рассмотрим семейство функций Нетрудно показать, что для выполняются условия: 5)

где Справедлива

Лемма 1. Пусть . Тогда для

Лемма 2. Пусть . Тогда для имеет место соотношение

Лемма 3. Пусть . Если для некоторых и при имеем то

Используем доказанные леммы при доказательстве следующей тео­ремы.

Теорема 1. Пусть и пусть момент останова в методе (3) выбирается по правилу (4). Тогда

Доказательство.

По индукции легко показать, что

Следовательно,

Отсюда

В силу лемм 1 и 2 имеем

Кроме того, из (5) и (6) следует, что

Применим правило останова (4). Тогда и из (11) и (15) получим . (17)

Для , поэтому . Итак, для

Из (13) и (18) получаем при или

(т.к. из (13) ). Если при этом при , то используя (10), получим так как из (12) Если же для некоторых последовательность окажется ограниченной, то и в этом случае

Действительно, из (17) имеем Следовательно, и по Лемме 3 получаем, что Отсюда ч.т.д.

Имеет место Теорема 2. Пусть выполнены условия теоремы 1 и пусть тогда справедливы оценки

Доказательство. Имеем Воспользовавшись (18), получим , откуда . При помощи неравенства моментов оценим

(см. (17)). Тогда, поскольку соотношение (5) справедливо для любых n,то ч.т.д.

Замечание 1. Порядок оценки (19) есть и он оптимален в классе задач с истокопредставимыми ре­шениями

Замечание 2. Хотя формулировка теоремы 2 даётся с указаниями степени представимости s и истокопредставимого элемента z, на практике их значение не потребуется, так как они не содержатся в правиле останова (4). И тем не менее в теореме 2 утверждается, что будет автоматически выбрано количество итераций т, обеспе­чивающее оптимальный порядок погрешности. Но даже если истокопредставимость точного решения отсутствует, останов по невязке (4), как показывает теорема 1, обеспечивает сходимость метода, т.е. его регуляризующие свойства.

Понятие корректно поставленной и некорректно поставленной задачи. Пример. Неявный метод простой итерации решения некорректных задач с априорным выбором числа итераций.

Пусть в гильбертовом пространстве Н требуется решить , где А – ограниченный, положительный и самосопряжённый оператор. Нуль не является собственным значением оператора, поэтому уравнение (1) имеет единственное решение. Предполагаем, что , поэтому задача (1) неустойчива и зн. некорректна.

Опр. Задача определения решения из пространства Х по известной правой части наз. устойчивой на пространствах Х и У, если Опр. Следуя Ж.Адамару, задачу отыскания из ур-я (1) наз. корректной (корректно поставленной), если при любой фиксированной правой части из У её решение: 1) существует в пространстве Х; 2) единственно в Х; 3) устойчиво в Х. Если хотя бы одно условие не выполняется, то задачу наз. некорректной (некорректно поставленной).

Пример некорректной задачи: Х=У=L₂(0,1). Интегральное уравнение Фредгольма 1-ого рода .

Опр. назовём задачу (1) корректной по Тихонову на множестве , а само множество М - её множеством корректности, если: 1) точное решение задачи существует в классе М; 2) принадлежащее множеству М решение задачи единственно для любой правой части у из множества ; 3) принадлежащее множеству М решение задачи устойчиво относительно любой правой части у из N. В случае нарушения любого из этих условий задачу (1) наз. некорректной.

Будем решать ур-е (1) с помощью неявного итерационного метода:

(2)

Предполагая существование единственного точного решения x уравнения (1) при точной правой части у, ищем его приближение при приближённой правой части , . В этом случае метод примет вид

(3)

Под сходимостью метода (3) понимается утверждение о том, что приближение подходит к точному решению х ур-я (1) при подходящем выборе n и достаточно малых , т.е. .

Справедлива

Теорема 1. Итерационный процесс (2) при условии (4) сходится в исходной норме гильбертова пространства .

Док-во:

По индукции нетрудно показать, что . Используя интегральное представление самосопряжённого оператора спектральная ф-я, . Так как уравнение (1) имеет по предположению единственное точное решение, то и, следовательно,

.

Разобьём полученный интеграл на 2 интеграла

При условии (4) величина , тогда

.

Следовательно, , т.е. итеративный процесс (2) сходится, ч.т.д.

Покажем, что при тех же условиях процесс (3) можно сделать сходящимся, если нужным образом выбрать число итераций n в зависимости от уровня погрешности . Имеет место

Теорема 2. При условии итерационный процесс (3) можно сделать сходящимся, если нужным образом выбрать число итераций n так, чтобы .

Доказательство:

Будем считать и рассмотрим разность . Как показано ранее, . Воспользовавшись интегральным представлением самосопряженного оператора , получим

По индукции нетрудно показать, что .

Тогда . Поскольку и, как показано ранее, , то для сходимости метода (3) достаточно, чтобы , ч.т.д.

Теорема 3. Если точное решение ур-я (1) истокопредставимо, т.е. , то при условии оценка погрешности для метода (3) . .

58 .Метод обобщенного суммирования рядов для решения некорректных задач.

При приближенном решении математических задач сущ. является вопрос корректно поставленной задачи.

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

Задача наз. корректной по Адамару, если при любой фиксированной правой части правой части y=y₀, точное решение: существует в x, единственно, устойчиво.

Задача наз. корректной по Тихонову на мн-ве X, если: точное реш. сущ в M, ед при любом у из N, устойчиво.

Метод обобщенного суммирования рядов предназначен для решения некорректных задач. Рассмотрим его на примере уравнения: в пр-ве L₂(0,1) c полным симметр. квадратично суммируемым ядром A(t,s). λ=0-принадлеж S(p), но не явл. его собственным значением. λi – собств. значения ядра, располож. в порядке убывания.

zi(t) – соотв. полная, ортонормированная система собственных функций уравнения: где, . В этом случае решение запишется:

Возьмем вместо точного y(t) – приближенное y_δ(t) такое, что , или, что то же самое, вместо точных коэф. Фурье – приближенные , . Требуется по этим точным приближениям коэф. Фурье построить аппроксимацию для точного решения. В этом случае решение запишется: - т.к. задача не корректна, то этим рядом пользоваться нельзя. Не будем доводить суммирование этого ряда до конца, а воспользуемся некоторым конечным отрезком: . Покажем, что это действительно можно сделать.

Рассмотрим: . Первый член справа , . Следов.: если n выбрать так, чтобы , то , при n=n(δ) →∞, для δ →0.

Оценить невозможно без дополнит. предположения, т.к. неизв., и может быть сколь угодно малой скорость убывания нормы. Потребуем чтобы x было истокопредставимо: . Из этого предположения следует, что сходится ряд x(t)=Az отсюда и что . Оценим , получим .

Найдем, при каком n эта оценка – оптимальна (принимает мин. значение).

, отсюда , з.н. t*- min.

Получим оптимальную оценку: при .

Если имеет место s-кратная истокопредставимость, то

Доказательство.

Так как и , то и

, т.е.

.

Следовательно, .

Отсюда

, ч.т.д.

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

Замечание 2. Использование энергетической нормы позволило получить оценки погрешности метода и априорный момент останова без требования знания истокопредставимости точного решения, что делает метод (3) эффективным и тогда, когда нет сведений об истокообразной представимости точного решения.

Стиль программирования.

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

Стандартизация стиля – правило: если сущ более одного способа сделать что-то и выбор произволен, то остановиться на одном и способе и всегда его придерживаться. Делая одно и тоже всегда одинаково легче избежать путаницы, однако процессу стандартизации свойственны и недостатки т.к. применение стандартов может замедлить работу, стандарты могут оказаться огранич или громоздкими для написания. Станд стиля – результат здравого смысла и опыта программистов, а не закреплённое раз и на всегда правило.

Комментарии – их редко вставляют в прогу, но потом авторы понимают что не помнят программу. Хорошее правило – включать комментарии в процессе написания проги, именно в это время программёр более всего шарит в проге.

Виды:

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

· Оглавление– если прога очень большая, то в её начале помещают оглавление виде комментариев(название, размещение и функции каждой подпрограммы)

· Пояснительные комментарии – сопровождают те части проги, к-рые трудно понять без комментариев. Норма – одна строка на 10 строк текста, комментарии должны описывать цель, а не объяснять синтаксис.

Расположение комментариев – выделяются пустыми строками, заключ-ся в прямоугольники, располагайте комментарии так, чтобы это не делало её менее наглядной. Коментарии должны быть должны быть правильными и изменяться в процессе изменения проги. Неправ комментарии хуже чем их отсутств.

Пропуски строк используются для отделения параграфов, рекоменд пропуск строки после опер безусл передачи управл.

Пробелы облегчают чтение, рекоменд ставить пробелу между элементами списка, +,-,:=.

Имена переменных должны быть выбраны так чтобы наилучш образом определить те величины, к-рые они представляют, если огранич на длину имени отсутств, используют имена настолько длинные настолько нужно, но не длиннее. Запреты: избегайте схожих по виду описаний, имена должны отлич психологич, цифры пишутся в конце имени, когда имя содерж избыт инф. это тоже плохо, в качестве индиф исп-ть те названия к-рые прим-ся в той области для к-рой решается задача. Для различных типов данных имена должны начинаться с соотв символов (dNorm, nIter). Имена файлов должны содержать «file».

Стандартные сокращения позволяют программистам понимать тексты прог. Соглашения Джексона: каждое значимое слово должно сокращаться но не больше 3-х, в аббревиатуру всегда должна включаться 1-я буква, согласные важнее гласных, начало важнее конца, аббревиатура должна включать 6-15 букв. Алгоритм: из слова удаляются все гласные с правого конца, пока либо все гласные не будут удалены, кроме первой, либо слово не уменьшиться до требуемого размера, если слово больше то удаляются согласные.

Перенос рекомендуется делать после знака операции. Это позволяет избежать ошибки, когда 2-я строка оператора может быть выброшена.

Размещение операторов – одного оператора в строке достаточно.

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

Скобки – в сомнительных случаях ставьте скобки, это не только делает прогу более понятной но и предотвращает ошибки, скобки обходятся дешевле ошибки.

Правильно сделанные отступы выявляют структуру проги, прога должна быть приятна глазу.

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

9. Проектирование программ. Структурный подход.

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

Программу снабжают комментариями, делят на параграфы, она становится ясной и точной. Одна из систем – один пишет, 2-й пытается понять написанное. Если 1-й не в состоянии дописать то 2-ой доделает.

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

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

Если предлагают выбрать язык, то подходящий для задачи язык высокого уровня – наилучший выбор.

Универсальностью будем н-ть независимость программы от конкретного набора данных. Хорошая универсальная программа должна обрабатывать вырожденные случаи и печатать сообщение об ошибке. Используйте в качестве параметров переменные, а не константы. Должна быть независимость проги от конкретного набора данных. { For i:=1 to 25 do read(a[i]), лучше Const N = 25;… For i:=1 to N do read(a[i]) }

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

Чтобы повысить эффективность прог, сохранить время на создание рекомендуется использовать библиотеки. Плагиат в программировании не преследуется. Встроенные функции лучше своих.

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

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

Более скромные по целям работающие программы полезнее неоконченных грандиозных проектов.

Цели: высокий уровень надёжности, выполнение нек-рого объёма данных к определ дате, миним время разработки или стоимость, эффект., универсальность, модифицируемость. Если прога должна быть сделана быстро и потом не будет модифицироваться то не надо усложнять. Наиболее важные параметры время и память, но есть ещё и сложность. Чем сложнее программа, тем труднее ее контролировать, тестировать, отлаживать и эксплуатировать. Устанавливайте цели проекта заблаговременно и точно.

Структурное программиров служит для организации процесса проектирования прог, те. чтобы предотвратить большинство ошибок и обнаруж те которые есть. СП сосредотачивается на логике проги и включ 3 составляющие:

· Проектирование сверху- вниз: метод предусматривает вначале определение задачи в общих чертах, а затем постепенное уточнение стр-ры путем внесения более мелких деталей. Сначала напишите прогу на естеств. языке. Прежде чем начать программ., разработайте проект. Исключайте ошибки с самого начала.

· Модульное программирование – процесс разбиения проги на модули и последующее их программирование. Каждая задача должна делиться на модули. Цели: необх добиться того, чтобы програмн модуль был правильным и не зависим от контекста, следует стремиться к тому чтобы из модулей можно было строить большие проги. Требования к модулям: короткие лучше длинных, независимость. Хороший модуль должен быть подобен математ функции.

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

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

Эффективность программ.

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

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

Обычно, большая часть времени расходуется на выполнение очень небольшой части программы (5% ее объема), называемой критической областью.

Требования к эффективности следует определять на этапе проектирования.

Отношение к эффективности

Существуют три типа программ по требованиям к эффективность:

1) часто используемые программы;

2) производственные программы (используются длительное время);

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

Следует оптимизировать те программы, которые используются многократно.

Оптимизирующие компиляторы

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

Типы оптимизации компилятора:

1) низкоуровневая (машинно-зависивамая) — на уровне элементарных команд, например, инструкций процессора;