На правах рукописи

ГРИНЕВИЧ Алексей Иванович

МЕТОД ОЦЕНКИ ПОГРЕШНОСТИ ОКРУГЛЕНИЙ

ЗНАЧЕНИЙ ВЫЧИСЛЯЕМОЙ ФУНКЦИИ,

ОСНОВАННЫЙ НА ВАРЬИРОВАНИИ ДЛИНЫ

МАНТИССЫ В АРИФМЕТИКЕ С ПЛАВАЮЩЕЙ

ЗАПЯТОЙ

Специальность 01.01.07 – вычислительная математика

АВТОРЕФЕРАТ

диссертации на соискание учётной степени кандидата физико-математических наук

МОСКВА – 2013

Работа выполнена на кафедре математических основ управления Московского физико-технического института (государственного университета)

Научный руководитель: кандидат физико-математических наук, доцент Бирюков Александр Гаврилович

Официальные оппоненты: доктор физико-математических наук, профессор Лобанов Алексей Иванович, кафедра вычислительной математики Московского физико-техинческого института (государственного университета), профессор доктор физико-математических наук, доцент Рогов Борис Вадимович, Институт прикладной математики имени М.В. Келдыша РАН, ведущий научный сотрудник

Ведущая организация: Вычислительный центр им. А.А. Дородницына РАН

Защита состоится _ 2013 г. в _ часов на заседании диссертационного совета Д 212.156.05 при Московском физико-техническом институте (государственном университете) по адресу 141700, Московская обл., г. Долгопрудный, Институтский пер., д.9 ауд. 903 КПМ.

С диссертацией можно ознакомиться в библиотеке Московского физикотехнического института (государственного университета).

Автореферат разослан _ 2013г.

Ученый секретарь диссертационного совета Федько О. С.

Общая характеристика работы

Актуальность темы В настоящее время большое внимание научного сообщества уделяется вопросам «вычислений с высокой точностью», т.е. таким вычислениям, при которых возможны изменения длины мантиссы машинного числа (МЧ) в широком диапазоне значений. Как отмечено в обзоре D. Bailey за 2012 г., можно выделить целый ряд направлений исследований, где стандартной арифметики оказывается недостаточно. Среди них есть как давно известные проблемы, так и относительно новые, активное изучение которых началось вместе с появлением достаточных вычислительных мощностей. Это моделирование солнечной системы за период в миллионы лет, вычисление рекуррентных соотношений, определение экспоненциально малых явлений в динамических системах, компьютерное исследование новых математических соотношений, моделирование явлений в сверхновых звездах и др. В частности, А. Фролов утверждает, что «сейчас мы научились рассматривать и решать задачу нескольких тел с ограничениями, о чем нельзя было и мечтать всего несколько лет назад». Для решения задачи им использовалась арифметика высокой точности (120 знаков) для нахождения собственных векторов почти вырожденных матриц размерами 5000x5000 в рамках решения задачи n тел.

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

1. Решение плохо обусловленных систем линейных уравнений (СЛУ).

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

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

4. Проблемы экспериментальной математики. Такие, как вычисление большого количества знаков в числах и e для установления возможной «нормальности», проверка гипотез о математических тождествах и т.п.

Время вычислений существенно возрастает (на 1-2 порядка) при переходе на «высокоточную» арифметику с варьируемой длиной мантиссы. Поэтому подобные вычислительные проблемы считались слишком трудоемкими до недавнего времени, и ученые старались изыскивать специфические методы решения для конкретных задач или упростить задачу до «разрешимого»

варианта. В последние годы ситуация начала меняться с появлением библиотек программ с интерфейсами высокого уровня. Здесь следует отметить и специальные подпрограммы для нахождения значений функций (ARPREC, GMP, MFPR, MPFR++, MPFUN90, QD), пакеты компьютерной алгебры, позволяющие находить решение символически без потери точности (Maple, MathCad, Mathematica) и реализации языков программирования, позволяющие задавать длину мантиссы (LISP, Python, Perl, Haskell, Ruby). При переходе на высокоточную арифметику, как правило, оказывается возможным не переводить программу целиком, а заменять лишь часть ключевых алгоритмов на более «точные» варианты. Это позволяет локализовать вычисления, требующие высокой точности и минимизировать влияние возрастающего времени выполнения до приемлемых значений. Таким образом, безусловно, вычисления в арифметике высокой точности не могут рассматриваться отдельно от других подходов по оптимизации вычислений. Поскольку набор практических задач, где необходимы высокая или заданная точность, продолжает расти, возникает вопрос о построении метода (методики) оценок погрешностей округлений при варьировании точности арифметики для получения заданной точности решения (ЗТР). Приобретают актуальность вопросы выработки обобщенных подходов и методов, применимых к широкому спектру задач в условиях арифметики высокой точности.

Таким образом, построение методов (методики) оценок погрешности решений задач вычислительной математики (ВМ), обладающих вышеуказанными свойствами, является актуальной научной проблемой.

Цели диссертационной работы.

1. Построение алгоритма вычисления значения функции применимого для достаточно широкого класса задач ВМ. Для предложенного алгоритма – исследование оценок погрешностей округления приближённых значений f x, зависящих от длины m мантиссы машинного числа (МЧ) и получение такого значения m0, которое обеспечивает достижение требуемой точности решения.

2. Разработка численных методов оценки погрешностей округления значений f x, гарантирующих достижение заданной точности (ЗТР), и исследование их свойств.

3. Численное исследование предложенных методов оценок погрешностей округления для некоторых классов задач ВМ.

Научная новизна.

1. Предложен численный алгоритм решения задачи ВМ, названный «Элементарный алгоритм вычислительной математики» (ЭАВМ), представляющий собой естественное объединение стандартных (базовых) вычислительных операций из какой-либо библиотеки программ. ЭАВМ обладает тем свойством, что при его реализации в точной арифметике будет получено точное значение вычисляемой функции.

2. Для ЭАВМ с конечным и бесконечным числом шагов (КША и БША) получены теоретические оценки погрешностей значений функции, зависящие от её аргументов и длины мантиссы m МЧ, гарантирующие достижение заданной точности решений.

3. Предложен метод К-решений (КР) – численной оценки погрешностей округления значения вычисляемой функции. Введены понятия итерационной последовательности значений функции с переменной мантиссой (ИППМ) и её g -устойчивости. Для g -устойчивой ИППМ доказана возможность достижения заданной точности решения.

4. Предложены алгоритмы, позволяющие оптимизировать процесс достижения заданной точности решения.

Практическая ценность. 1. Предложенный метод оценок погрешностей округления применим для достаточно широкого класса вычисляемых функций.

2. Метод не требует изменения используемых вычислительных алгоритмов.

Для получения значений погрешностей необходимо вычислить значения функции при разных длинах мантисс МЧ и сравнить их. 3. Предложен вариант метода варьирования длины мантиссы для получения заданной точности решения при решении задачи безусловной минимизации методом Ньютона.

Апробация. Основные положения диссертационной работы докладывались, обсуждались и получили одобрение специалистов на научных семинарах кафедр высшей математики и математических основ управления Московского физико-технического института (государственного университета) (2007-2013), научном семинаре отдела прикладных проблем оптимизации в Вычислительном центре им. А.А. Дородницына РАН (2013).

Публикации. По теме диссертации опубликованы 6 печатных работ, из них четыре [1, 2, 5, 6] из списка, рекомендованного ВАК РФ.

Личный вклад автора. Как содержание диссертации, так и основные положения, выносимые на защиту, отражают личный вклад автора в опубликованные по теме диссертации работы. Все представленные в диссертации результаты получены лично автором.

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

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

Для достижения требуемой точности решения рассматриваются оценки вида:

где f i, i 1, l – приближенные значения решений. Предложен метод Крешений (Глава 2) для построения функций оценок погрешности 1 f1,..., fl. Для того, чтобы оценка (1) выполнялась для, изменяющемся в некотором интервале значений, функции f1,..., f l, определяются при их вычислениях с различной длиной мантиссы МЧ. Факт достижения требуемой точности характеризует следующее определение.

Определение 1. Пусть задано 0 – требуемая точность вычисления приближённого значения f функции f, т.е. если точность решения задачи говорить, что имеет место заданная точность решения (ЗТР), если задача решается на ЭВМ методом, для которого известна функция оценки определяются вместе с искомым решением и для них выполнено условие Глава 1 диссертационной работы является вводной, носящей вспомогательный характер. Рассматриваются свойства машинного числа (МЧ) в формате IEEE 754; рассмотрены понятия машинного числа (МЧ), точности представления МЧ, функции округления МЧ и арифметических операций;

рассмотрены ситуациии потери значимости и переполнения, возникающие при выполнении арифметических операций; рассматриваются характеристики библиотек програм GNU GMP и GNU MPFR, в которых реализуется вычисление в арифметике с плавающей запятой базовых (стандартных) математических функций. Важнейшим свойством этих программ является то, что пользователь может задавать длину мантиссы МЧ в очень широком диапазоне от mmin 8 до mmax 646456993 десятичных знаков. Появление в свободном доступе программного обеспечения с такими характеристиками расширяет границы возможностей для получения решений широкого круга задач ВМ с гарантированной точностью высокого порядка. Диссертационная работа посвящена изучению погрешностей округления решений, значения которых получены для варьируемых значений длины мантиссы.

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

В главе 2 диссертации предложен алгоритм решения задачи ВМ, названный «элементарным» и исследованы некоторые его свойства.

В §2.1 вводятся определения понятий, на основе которых строится «элементарный алгоритм ВМ» (ЭАВМ).

Определение 2. Пусть : R R – некоторая функция, x R n – вектор, xm – его машинное представление. Тогда: (x), ( xm ) – значения функции в точках x и xm, m ( xm ) – машинное представление значения xm ; m x m ( xm ).

Значения функций x и xm в общем случае представляются бесконечным числом знаков; в этом случае будем говорить, что их значения получены в Определение 3. Математические функции и операции, реализуемые в библиотеках программ, реализующих математическую библиотеку стандарта ANSI С99, назовем базовыми или стандартными. К базовым операциям относятся: округление чисел, арифметические операции, логические операции, операции вычисления математических функций, таких как sin x, cos x, tan x, и Одной из библиотек, реализующих базовые функции стандарта С99, является GNU MPFR, в которой при заданной длине мантиссы m для значений базовых функции выполняется округление до последней значащей цифры, т.е.:

и m xm – значение одной из стандартных (базовых) функций, вычисленное в точке xm M b,m, p. Для случая, когда xm m xm xm 0. В (2) 1 b1m, b -основание системы исчисления, 0 погрешность нуля; она на много порядков меньше 1 (см. Главу 1).

Определение 4. Задачей вычислительной математики будем называть совокупность понятий и условий F ( f, x, m, ), определяющих возможность вычисления значений вектор-функции f : R R, где f x – решение данной задачи в точке x G ; – точность решения, m – длина мантиссы. Условие достижения точности означает: найти значение вектор-функции f m ( x) для которой выполнено одно из условий:

приближенные значения решений вычисляемые в точке x G для длин мантисс МЧ m, m1,..., ml.

Алгоритм решения задачи ВМ представляет собой композицию (объединение) базовых операций, т.е.

где символ означает объединение операций. Первый алгоритм вычисления f x является конечношаговым (КША), второй – бесконечношаговым (БША).

Оба алгоритма (3) и (4) рассматриваются в точной арифметике.

Соответствующие КША и БША алгоритмы для вычисления f m x представлены следующими формулами:

N 0 – число шагов БША, которое определяется по некоторому правилу его окончания.

Определение 5. Алгоритм вычисления функции f R (5) в точке x R n при длине мантиссы m будет называться элементарным алгоритмом для решения задач вычислительной математики (ЭАВМ), если вычисленное значение функции в точной арифметике по алгоритму (5), в котором логические операции не выполняются, дает точное значение функции f (x), т.е. имеет место:

В §2.2 изучаются погрешности округлений, возникающие в итерационном процессе ЭАВМ.

Лемма 1. Пусть i – базовые вычислительные операции (кроме логических) из некоторой библиотеки программ, i [1, Nб ] – номер базовой операции. Тогда значение m (ai ) можно представить в виде – число базовых операций библиотеки, | i | i (ai ), 1 b1m, ai R s, ai am,i Лемма 2. Пусть для чисел d, y, z и их приближенных значений d m, y m, z m Лемма 3. Пусть функция : R R удовлетворяет условию Липшица:

– компакт. Тогда существуют такие числа li L, L, что Теорема 1. Пусть функция f x R, x G Rn ; базовые функции i (ai ) (кроме логических) либо являются функциями округления числа, либо непрерывны по Липшицу, т.е. в некоторой окрестности i (ai ) точки ai R s удовлетворяют условию: i (ai ) i (bi ) Li | ai bi |, i [1, N ], а алгоритм (3) вычисления функции f (x) что Определение 6. Пусть в бесконечношаговом алгоритме выполнено N первых базовых операций и для f (x) получено приближение значения вычисляемой функции f m ( x). БША вычисления функции f называется элементарным, если Определение 7. Бесконечношаговый алгоритм называется сходящимся, если f ( x) lim f N ( x), где f x – точное решение задачи после N операций БША.

Из доказательства теоремы 1 следует, что для ЭАВМ решение задачи представляется как:

длина мантиссы МЧ. Анализ формулы, приведенный в Следствии к теореме показывает, что решение (11) возможно представить в другом виде:

Если БША решения задачи является сходящимся т.е. f x lim f N x, где f N x – точное решение задачи после выполнения N операций его определяющих, то результат теоремы 1 уточняется.

Теорема 2. Пусть для функции f m x БША является элементарным, сходящимся и выполнены условия теоремы 1. Тогда существуют векторы C R k, R, такие, что 0 : имеет место представление В §2.3 получены оценки длины мантиссы, гарантирующей достижение требуемой точности ЭАВМ решения задачи ВМ для КША и БША.

Определение 8. Будем говорить, что метод (алгоритм) вычисления значения функции f Rk называется корректным (КМ), если для любого 0 найдется такой размер мантиссы m, что:

Определение 9. Будем говорить, что значение функции f m ( x) имеет погрешность порядка, 0 1, относительно погрешности мантиссы, если существуют константы C и C0 такие, что x G Rn, C C, C / f x C0, m mmin, где mmin – минимальное значение длины мантиссы при которой могут проводиться вычисления и Векторы C в формуле (10) (или C в (12)) назовем параметром погрешности (ПП) значения функции порядок. Тогда для любого 0 данный метод вычисления функции будет корректным при m 1 1 log b или m 1 1 log b, где A - целая часть Таким образом теорема 3 (и 4) дают условия, при которых имеет место заданная точность решения (ЗТР). Конечно, верхнее значение длины мантиссы, необходимое для обеспечения ЗТР, не может превышать максимальных значений, которые имеет используемая библиотека программ. В частности для пакета Maple mmax 65535 десятичных знаков, а для GNU GMP mmax десятичных знаков.

Теорема 4. Пусть БША является сходящимся и элементарным, для каждого N выполнены условия теоремы 2, погрешность округления для каждого N в (13) имеет порядок ; т.е. C1 C b m, 0 1 и выполнено условие C C x G, m mmin, где mmin – минимальная длина мантиссы при которой могут проводиться вычисления. Тогда существуют такое число базовых операций N и такая длина мантиссы m, при которых достигается требуемая точность решения Глава 3 диссертации посвящена построению вычислимых оценок погрешностей округлений значений f m x.

последовательности с переменной мантиссой (ИППМ).

последовательностью с переменной мантиссой (ИППМ) решения задачи ВМ.

Определение 11. Числа и 0 называются малыми по сравнению с 1, если 0 0 0,1. Условие малости чисел по сравнению с 1 обозначается символом Последовательность решений задачи назовем g -устойчивой, если gi g0 1, i 1, L 1. Число g i, i 1, L 1 назовем коэффициентом уменьшения (КУ) Для упрощения изложения представим значение погрешности для частного случая его порядка 1 :

где b – основание МЧ. Тогда очевидно, что при достаточно большом значении m, и Cm C, где C не зависит от m, может быть малым числом.

Лемма 4. Пусть для ИППМ выполнено условие (17) и погрешности:

i 1, L 1], что g i g 0, g0 1, где g 0 – заданное малое число, т.е. ИППМ g устойчива.

Приведем достаточное условие g -устойчивости ИППМ. Рассмотрим некоторые оценки погрешностей решений задач ВМ для g -устойчивой ИППМ.

Лемма 5. Пусть ИППМ g - устойчива. Тогда для значений погрешностей i, j, ij имеют место двухсторонние оценки:

Теорема 5. 1. Пусть в ИППМ выполнено условие Для того, чтобы значение функции f m x было К-решением, необходимо и j достаточно, чтобы ИППМ была g -устойчивой. 2. Пусть ИППМ g -устойчива.

Из П.2 теоремы следует, что существует такой номер i ИППМ, для которого имеет место ЗТР 0. Номеру i соответствует длина мантиссы mi, которая, конечно, не должна превышать значения mmax библиотеки программ.

Препятствием к практическому применению полученных оценок является значение g ij, в котором присутствует «истинное» решение f x, в общем случае неизвестное при вычислениях.

Для практического применения указанных оценок вводятся новые понятия.

Определение 14. Пусть f m x – КР задачи ВМ. Обозначим L назовем квазиустойчивой (или g iL -устойчивой по отношению к КР), если В леммах 6 и 7 приводятся оценки, связывающие теоретические значения для коэффициента уменьшения g ij и вычисляемые на практике величины g ij.

В теореме 6 рассматриваются оценки погрешностей округления для g устойчивой ИППМ, которые можно применять при численном решении.

i 1, L 1, ИППМ g -устойчива, f mi x i, i 1, L. Тогда имеет место оценка корректирующие множители погрешности решений. Машинное значение числа В §3.2 рассматриваются подходы к практической оценке погрешностей, получаемых в процессе построения ИППМ. Исследованы алгоритмы построения оценок погрешностей округлений.

В разделе 3.2.1 рассматривается алгоритм последовательной оценки погрешности округлений решений. Задается некоторое начальное значение длины мантиссы m m1. Следующие значения длин мантиссы задаем по правилу mi 1 mi mi 1, i 1,2,.... Особенностью настоящего алгоритма является то, что оценка погрешности округления (ОПО) задачи ВМ проводится после каждого решения с мантиссой большей длины. При решении задач ВМ возможны различные схемы получения ОПО. Выделим две основные схемы.

Пусть f m x и f m x – решение и К-решение задачи ВМ.

1. Пусть задана требуемая точность решения A и для некоторых решений f m x, f m x выполнено неравенство: i Aij 1 A. Тогда полученная относительная погрешность решения 1 удовлетворяет условию:

погрешности, т.е. выполняется неравенство:

абсолютной погрешности решения 1 выполняется условие:

В оценках (20) и (21) значению функций 1, из (1) соответствует функция для относительной погрешности.

абсолютная погрешность его не более A : i i,i1 /(1 g0 ) относительная – 0.

условия 3 3bm 0 fm x. Считаем, что 3 1, где можно брать равным условие ВМ и значение 1 23 /(1 g0 ). Если не выполнено, то далее ИППМ реализуется по Варианту 1 при mi 1 mi im, i 3.

В разделе 3.2.2 (П2) рассматривается табличный алгоритм оценки погрешностей округления решений. Пусть ИППМ решений представлена в задает Вычислитель (лицо, решающее задачу ВМ). Построим таблицу значения i, j i. Строится также таблица чисел g ij и таблица оценок 0 1 t0, t0 0,1 и т.п. Совокупность всех указанных таблиц дает информацию о величине погрешностей решений f m x, i 1, L 1, и об g -устойчивости ИППМ.

В разделе 3.2.3 рассматриваются методы округления решений. Полученное значение функции представляется как f m x mi -значное, т.е. представление решения в 10-ичной системе имеет mi 10-ичных знаков. Значение f m x i округляется до t знаков, t < mi.

В §3.2 рассматривается естественное обобщение сформулированных выше правил округления на случай k 2, т.е. на случай вектор-функций.

В §3.3 исследуется метод оценки погрешности округления скалярных решений по правилу «совпадения t первых десятичных знаков».

В §3.4 показано, что при g -устойчивости БША для них справедливы все результаты теории, сформулированные в разделах 2 и 3, а потому методика получения заданной точности решений для БША будет той же, что и для КША.

В §3.5 рассматривается вопрос эффективности предложенного подхода.

Метод КР обладает значительной универсальностью в определении погрешностей округления значений функции, т.к. он не ориентирован на какиелибо классы решаемых задач. Таким образом, если метод КР решает задачу за приемлемое время, а традиционный метод (ТМ), использующий «стандартное»

программное обеспечение решает, но не дает ЗТР, то метод КР можно считать высокоэффективным по сравнению с ТМ.

В главе 4 анализируются результаты численных экспериментов, проделанных для проверки предложенных теоретических результатов. Для практических целей использовался математический пакет Maple 13, в котором регулировка точности вычислений производится в соответствии со стандартом IEEE 854, который является расширением стандарта IEEE 754 на случай b 10.

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

В §4.1 рассматривается задача вычисления полинома. Рассмотрена зависимость погрешности от m и точки x.

В §4.2 рассматриваются различные варианты методов решения СЛУ:

метод Гаусса с выбором главного элемента. Рассмотрим задачу нахождения решения системы линейных уравнений (СЛУ):

Рис. 1. Левый график: Зависимость абсолютной погрешности решения СЛУ (23) m от длины мантиссы m. Правый график: Зависимость t – времени решения от длины мантиссы m и размерности СЛУ ( K 10,20,30,40 ) Из первого графика (Рис. 1) видно, что зависимость погрешности для плохо обусловленной матрицы имеет зону неопределенности, после чего выходит на участок эксспоненциального убывания вместе с ростом длины мантиссы. На этом участке проявляется свойство g -устойчивости.

Рис. 2. Зависимость в области стабильности ( m 60 ) и области роста ( m 60) для СЛУ вида ((23) от длины мантиссы m при K 40 и шаге изменения На графике (Рис. 2) представлено значение параметра погрешности зависимость параметра погрешности от m при m 45 можно трактовать как постоянное значение, на которое наложено «случайное» возмущение.

Рассмотрим различные правила варьирования длины мантиссы МЧ (ПВМ) для для нахождения решения задачи ((23) с заданной точностью 0 10 20 в условиях ИППМ:

Для всех правил m1 100. Критерий остановки варьирования: i1,i2 0,1 и ИППМ;

ПВМ №1 clog: Правило, на основании П1.2 Вариант 2, описанного в п. 3.2.

графиков для, рассмотренных выше.

ПВМ №2 lin10: ПВМ №2. mi 1 mi m, m ПВМ №3 lin20: mi 1 mi m, m ПВМ №4 2x: ПВМ №4. mi 1 2mi мантиссы.

ПВМ №6 m1000: mi 1000 – правило с достаточно большой длиной мантиссы и единственным вычислением.

Эксперимент проведён для матриц Гильберта порядка N=100,200,300.

Таблица 1. Зависимость времени решения t для СЛУ вида ((23) от ПВМ при N 100, 200, 300, где mi – достаточная длина мантиссы, - истинная погрешность полученного решения, iL – практическая оценка погрешности, i – число шагов Из результатов эксперимента (Таблица 1) видно, что подход с варьированием мантиссы позволяет получать решение с требуемой точностью вне зависимости от способа варьирования. Далее в работе для решения СЛУ с матрицей Гильберта рассмотрен метод сопряженных градиентов. Произведены оценки коэффициентов g ij и их сравнение с теоретическим результатом. На основании этого сделан вывод о g -устойчивости данных методов. Рассмотрено поведение параметра погрешности C x, m.

В §4.3 рассматривается задача численного нахождения производной.

Показано, что параметр погрешности 1 / 2 при соответствующем выборе шага дифференцирования h ~. Изучен вопрос g -устойчивости ИППМ для этой задачи.

В §4.4 задача нахождения собственных чисел методом Данилевского. На эксперименте показано, что ИППМ для метода Данилевского является g устойчивой начиная с некоторой длины мантиссы m.

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

Задача БМ Б (Функция Розенброка 1) 0, p 1,2,3.... Для функции (24) известно точное решение – xi* 1, i 1, n, а значение f x* 0, причем решение (точка x* ) у этой функции – единственное.

При численном эксперименте принимались следующие общие условия:

1 2 1020 – требуемая точность. При такой величине требуемой точности, стандартной арифметики двойной точности уже недостаточно и варьирование мантиссы становится необходимым.

минимизация происходит с помощью метода золотого сечения. Причем Для нахождения требуемой длины мантиссы использовались различные ПВМ. Общий подход к реализации ИППМ состоит в использовании последовательности длин мантисс mg m1 m 2 m3..., где g 1,2,... – группы вычислений с указанным значением мантиссы. Для каждой группы вычислений определены следующие параметры: 1. Требуемая точность для данной группы:

i max 10 3, 1. 2. Параметр перехода. Способ определения точности для каждой группы: mi 1 T (mi, xk, F ). Для первой группы m1 T1 x0, F, 1. 3. Шаг При вычислениях в каждой группе используются следующие условия окончания: Условие окончания 1: Если xk xk 1 i, то происходит увеличение мантиссы и вычисления продолжаются для следующей группы начиная с достигнутого xk. Условие окончания 2: Если количество шагов в данной группе превосходит n N i, то происходит переход к следующей группе. Условие окончания 3: Если на любом шаге группы срабатывает более сильное условие полного окончания а) то алгоритм считается завершенным.

Рассмотрены ПВМ, аналогичные приведенным ранее для СЛУ:

ПВМ №5: (m*): использует m* – наименьшую из достаточных точностей полученную на одном из предыдущих шагов. mi 1 mi, m1 m*.

ПВМ №6 (m100): В этом подходе фиксированная достаточно большая длина мантиссы 100, т.е. mi 1 mi, m 100.

Таблица 2. Время решения задачи (24) с ЗТР 1 2 1020 с помощью различных ПВМ, градиент вычисляется численно. x xk – погрешность полученного Сравнительные результаты применения различных подходов к варьированию мантиссы показывают, что предложенный адаптивный подход (ПВМ №1) для предсказания m, в целом дает эффективный метод для варьирования длин мантисс в ИППМ.

В заключении приведены основные результаты диссертации.

В приложении 1 рассмотрены различные подходы к варьированию мантисс применительно к методу штрафных функций.

В приложении 2 рассмотрены сеточные методы для решения задачи Коши и уравнения теплопроводности. В частности, исследован вопрос о возможности связывания шага сетки h с длиной мантиссы m по аналогии с задачей о численном дифференцировании.

Основные результаты диссертации 1. Введены понятия элементарного алгоритма решений задач бесконечношагового (БША) алгоритмов. Для элементарного алгоритма получены оценки погрешности решений как для КША, так и для БША, зависящие от длины мантиссы и аргументов алгоритмов. Для КША получены оценки длины мантиссы, обеспечивающие достижение требуемой точности значения функции.

2. Введены понятие контрольного решения (КР) задачи, которое в оценках погрешностей решений с некоторой точностью заменяет истинное значение функции и понятие g -устойчивой последовательности решений.

Исследованы свойства g -устойчивости, в том числе доказана теорема о достижимости заданной точности значения функции; получены оценки погрешности, далее численно реализуемые в итерационной последовательности с переменной мантиссой.

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

Рассмотрены методы округления полученных решений, причем округленное решение имеет заданную точность.

Автор выражает глубокую благодарность своему научному руководителю доценту Бирюкову А.Г. за постановку задачи, ценные советы, терпение и постоянное внимание к работе.

Список публикаций автора по теме диссертации 1. Бирюков А.Г., Гриневич А.И. О гарантированной точности решений задач вычислительной математики в арифметике с плавающей запятой и переменной длиной мантиссы // Труды МФТИ. – 2012. – Т.4, №3, С. 171Бирюков А.Г., Гриневич А.И. Метод оценки погрешностей округления решений задач вычислительной математики в арифметике с плавающей запятой, основанный на сравнении решений с изменяемой длиной мантиссы машинного числа // Труды МФТИ. – 2013 – Том 5, № 2(18), С.160-174.

3. Гриневич А.И. Математическая модель погрешностей округления при вычислениях в арифметике с плавающей запятой и переменной длиной мантиссы. // Труды 55-й научной конференции / Управление и прикладная математика. Том 1. – М.: МФТИ, 2012, С.15-16.

4. Бирюков А.Г., Гриневич А.И. Итерационный процесс с переменной длиной мантиссы для решения задач вычислительной математики с заданной точностью // Труды 55-й научной конференции / Управление и прикладная математика. Том 1. – М.: МФТИ, 2012, С. 86-87.

5. Бирюков А.Г., Гриневич А.И. Анализ погрешностей некоторых алгоритмов безусловной минимизации. Труды Института системного анализа РАН.

Динамика неоднородных систем. Том 42(1), 2009, С. 106-111.

6. Бирюков А.Г., Гриневич А.И. Об эффективности и устойчивости численных методов решения систем нелинейных уравнений и задач безусловной минимизации // Труды Института системного анализа РАН.

Динамика линейных и нелинейных систем. Том 25(1), 2006, С. 111-123.

МЕТОД ОЦЕНКИ ПОГРЕШНОСТИ ОКРУГЛЕНИЙ ЗНАЧЕНИЙ

ВЫЧИСЛЯЕМОЙ ФУНКЦИИ, ОСНОВАННЫЙ НА ВАРЬИРОВАНИИ

ДЛИНЫ МАНТИССЫ В АРИФМЕТИКЕ С ПЛАВАЮЩЕЙ ЗАПЯТОЙ

Подписано в печать 12.04.2013. Формат 60 84 116.

Федеральное государственное автономное образовательное учреждение высшего профессионального образования «Московский физико-технический институт (государственный университет)»

Отдел оперативной полиграфии «Физтех-полиграф»

141700, Московская обл., г. Долгопрудный, Институтский пер.,