автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.16, диссертация на тему:Комплекс алгоритмов дискретного перебора для геохимических расчетов на ЭВМ

рго од

4 !! ИМ» 'ЩОТРСКИЯ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

па правах рукоготои УДК 619.ББ4

ГУТМАН Татьяна Давидовна *

КОМПЛЕКС АЛГОРИТМОВ ДИОНРЕТНОГО ПЕРЕБОРА ДЛЯ ГЕОХМШЕСКИХ РАСЧЕТОВ НА ЭВМ

/■

Г

<

ОБ.13.16. - применение вычислительной техники, матемвтическкк методов и математического моделирования в нэучвшх исследованиях в отрасли химических пая« /*

''

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата СЕязико-математических наук

• \ • \. .

ч

' л •

г

V

УФА - 1993

Работа выполнена в лаборатории физико-химических методов исследования Института геологии УЩ РАН

Научные руководители: доктор физико-математических наук, .профессор и. Д. Рамазанов!

кандидат физико-математических наук А. М. Курмангелеева.

Официальные оппоненты5 доктор технических наук, профессор ЭЛ. Мухачава|

кандидат физико-математических наук Н, К, Бвкиров!

. Ведущая организация! Научно-исследовательский институт по повышению нефтеотдачи пластов

Защита состоится %?£" ^нал 1993 г. в "_" часов на

заседании спацивлизироащгаго совета K064.I3.03 при Башкирском государственном университете по адресу! 450074( г. Уфа, ул. Фрунза,.32, ауд. 511.

• С диссертацией мокно ознакомиться в библиотеке Башкирского государственного университета.

Автореферат разослан "23, "¿.»км 1Э93 г.

< , Отзывы на автореферат, -заверэнные.гербовой печатью, просим высылать по укааарому адресу на имя ученого секретаря специализированного совета K-064.I3.Ö3 Морозкина Н.Д.

Ученый секретарь специализированного совета K064.I3.03 MJL-- Морозкин Н.Д.

ЬВследствие интенсивного развития нейтронно-пп-тиваиионного, рентгено-флюоресиентного и рада других фиэико-хими-чепких методов определения содержания химических элементов, полнилась возможность применять геохимические методы поиска и локализации рудных и колчеданных месторождений, основанные на комплексном анализе процентных содержаний в геологических образцах десятков химических элементов й соединений. В связи с этим возникла потребность в новых вычислительных процедурах, включающих как составные элементы традиционные задачи геохимии - выделение кластеров в пространстве классификационных признаков (1Ш) и их границ, а Также задачу преобразования КП путем нормативных пересчетов из одних аддитивных структур над содержаниями химических элементов - в другие. Границы кластеров определяются по аналитическим или геометрическим ограничениям, обычно формулируемым в виде неравенств, трансцендентных уравнений и систем трансцендентных уравнений. По-птому необходимо, чтобы реализующие яти операции процедуры были применимы к расчетным объектам произвольной структуры, не нуждались и визуальном анализе исходных и промежуточных результатов и представляли выходные донные в удобной для дальнейшей обработки форме.

Цель работы. В работа предлагаются алгоритм, предназначенные для задач классификации, определения границ кластеров или точечных конечно связныа множеств, заданных- произвольными шчиолтшмя ограничениями; задач решения систем трансцоденталыгах уравнений иа двумерной плоскости и в многомерном пространстве; алгоритм оптгаи-. зацая аддитивной функции по набору ранжированная критериев я системе нелинейных ограничений. Эта алгоритмы продиазначонн для расчетов, в которых неприменим штода направленного поиска; для сложных внчяслений а автономном реяяме на ЭВМ, включающих их в качества составных элементов. Точность и сходимость алгоритмов не завяоят от стйгктурти характористяк расчетных объектов. Ш-

хадане данниэ олгоритмов представлэнн в вкономичной форма, допуска-щай обработку на ЭВМ Саа предварительного виауалыюго анализа. Метод исслзловвная. В качестве основных: инструментов исследования применялись некоторые даокрагазированные понятия топологии кривых tía плоскости в даффоракцнольного анвяиаа| гооматрия на клеточном растре и динамических последовательностях вложенных

параллелепипедов! набор модификаций метода ветвей и границt ириешх оптимального перебора, принятые в вычислительной комбштторихе. • Научная новизна. Сформулированы и доказaim нокотоуыа теорем о граничных точквх "белого" ' кнокзстви на клеточном плоском бинарном черно-Сэлом раотро. С помощью btíjc теорем раарвботан комплекс влгорямов F1, который но клеточной сети R, выбранной в вашскмости от требуемой точнооти и ограничений на оперативную память ЭБ.Ч и время счета, генерирует ориентированную границу "белого" клеточного множества. S1 по ряду параметров работает более точно и вкономично, чем аналогичные процедуры, принятые в растровой электронике. Кроме того, выдэляемие границы оптимизируются по числу представляющих их контуров и суммарной длине. Последнее важно при йх использовании без предварительного визуильного анализа в дальнейших расчетах.

Разработан алгоритм FAST выделения границы плоского конечно связного точечного множества, включающий Г1 в качестве основного блока. Его точность не зависит от топологических характеристик искомой границы, á время счета пропорционально суммарной длине искомой границы и длине ввена сети Я.

Разработан алгоритм ФАСКИ равбивния на кластеры точечного

т

множества U в многомерном пространстве X - X-¡xX^.. основанный на последовательном разбиении ¡I в шгаскоотях JCjxXj на компоненты связности на сети vxv, где v определяется алгоритмически в процессе

работ CACETI • Такой порядок кластеризации обвсгсвчнраэт устойчивость относительно нолдюйгаога crr.icTt гяиду ?глвссшфик8даошщкн napa-¡íQTpEw.í цри r-iicoKoü рвамариаотц ет пространства X , в такяо допускает величие качественна рстгфзртшаа кяаоривяивцвощиг параметров»

Прэдлигпвтоя понятия "почетного " а/О-корпя систеш» трапсцовдонппп ypaxîî'Rin-Tî п алгоритм ЕХГД решвтшя' в айцем гтдо щюиополшоЗ едатвмц трятоцеа^слтишс уращгвшгЗ па провополыгаи пзроллалогшпада П s пршятсЗ тордашлопш. При о том точность ЕХТН ограничона лшь погрзпяоотьй ясхадиах двщшх и вкстргщоляциспного алгоритма, а саодадоотъ на зпеноит от юаадэнш рэпчаишх фуикцкй па пвраллвлапипвда П.

Скорму "гроваиа п падач оп-гдегавита лжгрйкыг

фущщна о нэлга!айшш огрзшгчзингсс! нэ?од1ид OIPíT нормативного парасчата ввцэотваинога састапо геологически ойразцов в ЮТЕшраль-Eitt, что позволила рэялизояпть аз на ГЛП я яяда, допусгшкгда шздфзкпцпв иэтодякя н ккгзкзша списков рзочвткнх огаодоо к (зюэралов йоо нриэлмгся расчетной cxst.si гтрогргмль

Все првллегрошз в рг.батэ влгортз! роапазааш иа ЗШ тала ЕЗ з (mat) ID!} ГЗ АЧ\ щгмонялзст. г. гсоспкпэстт расчетах} еасягао дшшх кадт-цспокся даагкост'пслг птсгйоЯ £якаш (см. пр?!Лог'.знчя 1-3), Эксплуатация прогрев; подтг-вр^ма пригодность алгоритмов ялл экслрзсо-аштгао пря отоуютсая свраорпях херяамрпот? аяалггкруслиг (или иcv.oiixz) объектов, а тскяз сосмспгаогь пр.гз:зпскгм в-торппло;: п качаатгя составных вламентов слсгзшх расчатсп на Ж!| a qstoiiomícm panais. 15мвтся заключение ой оксипуатацип nporpRî.si» ревлнзувдих алгоратад FAST я ЕХТЛ в лаборэторга фязика а тот« столкновэнкЗ Отдала фазшз УРО ВКЦ АН CCCPj акт внедрения программной реализации алгоритма ФАСЕТ! па кефэдре гоойяталЪноЙ тдкогркл Уф-шсного медицинского

к-;ап?тута1 служебная записка по геохимической интерпретации р&зультвтов расчетов по ФАСЕТ1 при петрографическом анализа горних пород в лаборатории магматизма Института геологии Уфимского ©сдала РАК.

ijfnqaeigH pijfioT^. Ошюшша результаты раОоти докладывались на войЁзрэицыц молод« сшцавластов БШ1 СОСР (1885 г.)| на конференции "Пробло»щ геологии, юшералогки, геоик.ши полашшх Виаоавэшх Бвдого Урала а соцрвдвлышг территорий, АН СССР, IB09 Г.5 на кокфэрощад "Цатвыртачеоиое программирование и прилокеиш". ■Оодрйяово!:» УРО ДН СОСР, IKH г.

Ооцааш^э рааультотц даосертацаошюй работы опублкковаии з црэпршта и статьях 11-65.

tyroyEWPa и РбЦн работа. Дцссирцщия саотаит из пвадвшш, оеми вохлтвшя, опкксе цктнруекой литературы, оодаравщаго 54 ooijjasu ка пэрвоя о точюши, И прилокеша 1-3. СОъам работы ооотааляэ? 133 стршсщ,

ООДЕР&ЛИЕ ДКОСЕРТАВДИ

Клаеокфккзцяошый ввдача о взотко ввдэшшмн уелоанкет и огрсначвнпщш часто входят в качество аосгвшшх алокентов в слоеные внчнолитольшз процесса. Прл размикя таких задач на пэрсыЗ план шготупеот у шьорейг.ы:оать расчэтоа| нэзЕЕзс:ак>сть их точноота от структурных лврактэриоткк анапыаируеиж оОмкюя) вромя счета| козмоанооть реализации алгоритмов в автономной рзгша, Оаа шауального анализи промежуточных результатов} получопиз шходных дщаадс в фзрмо, удойной для дальнейшей обработки на ЭВМ и ( или ) грсвэиня в дисковой памяти ЭВМ.

В этом случаэ представляется целесообразным вводить промэку-

точные представления объектов - юс приближения на Некоторых ( воз-вовМокнй, динамических, клеточных косрдииапшх сетях ( растрах ), порядок ивменения которы! монет определяться как априорно, тек и в процессе расчетов. В данной работе предлагаются алгоритмы PAST, ФАСЕТ1, EXTR, использующие в комплексе представления датшх как в евклидовых пространствах, так и на динамических раотровых клоточянх сетях, с переменной длиной звена координатной сети.

Сведение Приводится краткий анализ областей применимости предлагаемых алгоритмов! обоснование их новизны | актуальности решаемых ими задач. Формулируются основные результаты, полуЧейные В диссертации.

Глава I. Теоретические основы алгоритма FAST В п. I.I формулируется постановка задачи и обосновывается обобщенная схема PASTt

Пусть на прямоугольника П задана непрерывна^ функция г(х,у). Требуется выделить ориентированную границу точечного множества V -( (х,у) | r(x,y) z О ). Иначе Говоря, для квкдой компоненты связности RS грагегцы мнояоства V требуется сгенерировать 0-оеть точек, пронумерованных в порядке некоторого непрерывного обхода KSJ в > О - заданное достаточно малое число.

Отметим, что по схеме, реализующей FAST, решается и задача определения ориентированных границ точечного мнскества ТЫ по произвольным вычислимым ограничениям при единственном условии! Г!f -конечно связное ограниченное множество.

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

(I) Переход от значений характеристической функции f(x,y)

Т

анализируемого точечного югаааотвв, заданного иа дискретной нерегулярной с в та точек, - к приближающая ее сеточной функции р(s,у), веданной нв узловых точках координатной клеточной сети Я по алгоритму REGYL |

(2) Еадэлениэ ОрИеН'ГИрОЭ£12ЩОЙ ГрВШЩЦ KÏÎOSC9CTBQ p(Xt 1J} У'ИЗ сотп Я по алгоритму FI |

(3) Переход от найденных ломаных границ - к уточненным Ьриэнткроввшшм кривым по алгоритму ACCUE .

В п; 1.2. излагается принцип реализации алгоритма F1*

Алгоритм F1 отличается от традиционных методов выделения границ "болых" множоотв на чарно-белэм клеточном растре тем,что1

(1) Нэ кокеааат топологической структуры анализируемого "белого" множества на чорш-болом клеточном раотрэ j в том числе, сохраняет точки касания компонент связности его гранит

(2) Искомые границы представляются в оптимальной форма по даум- критериям, следующим ниже в порядке их значимости! число ввшшутых ломаных, представляющих границу | га суммарная длина)

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

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

Алгоритм F! решает задачу! Задана сеточная двузначная функция

на' прямоугольнике П, пришшавдая значения I и -I в узловых

точках клеточной оети Я. Трабуатоя выделить ориентированную границу точечного инозества V = ( (х,у)(х,у) r^-клесчеЛаи.опрвмвлеиио.Ю

Определение I. Назовем ré- wwoJ узловую точку сати К па пря иоугодыцам П, для котороЗ r(T) i О; г_-тотаоа - точку, для которой r(T) < 0| r+ -няа т;:оЯ - клэтку пет-.! Л, а углоазд точках которой -г+-точки. г+-вввном - castra оети Л, на концах которого - г^-точк:. }1ввовш jasTovincj шсшотяом ив о а та Я точечное мнокастао, равцоо объвдшшюда некоторой совокупности клеток сети Я.

Определение 2. Ипзоезм функция г(Т) регулярной сэточной функцией» золя для даЗой ' точка KKiroüHRaxoai орэда чвтырек соседних о mtt г^-гачвх азти R есть на Оолаа двух внутренних г_-та-чак пряыоугальшгка П.

Очавщго i чтойа отогаетваякв го г+-гочкш не глогло ■ аачватп в тугож, необходим а достаточно, чтоец фушцяя г(Т) бы.ча регулярной.

Опрэдолзвдэ 3. hc301?2!5 бВрегуЛЯртоЗ оэточноя йпзй|2в2(

если кзядйя угясвзя гу-точка пргакачлоп« пэтотороЗ г^-клэткэ. .

Очепвдю, эола Оуг зсцкя rf?; б:1рэгуляр:га, Ч ooctont í.-:; г+-клв*он. Рассмотрим асрунтгру клзточного кгаггаотиа 7« .

Опредвлаккв 4. Z-щаяаЯ будчя кзсиезть зекадутув проотря ломаауя» ооотокцув на гу-взвиь4а п эсвкьэв, лвгзавх на грвщша прямоугольника П.

Определение б, Пусть ШIT - некоторое переменное инояеотво уклонах тачек азти Л, лзявяра на прямоугольнике П. Придадим 1<К? начальное значите« ШГГ :« 0.

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

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

0 граничащих ташц, что вое узловые точки оатв А внутри кавдов области Р ч? Мр я,вл.1»твя 1%-тачквмц (ила г_-точками).

Прибавим ко цножватву ЫШ рое узлавне точки авти Я, лвквщие на ввмнквдаях беаовцх областей кулевого порядка« Присвоим новое взачэкие № переданной МН?(1 ШТ,;» ШТ.

2 итерация. / Базовой областью пэраого порядка считаем произвольный максимальный влемант ив множества 1Шг областай,

01 рщичаккцх Я-кривыш, таких, что воа узловые точки сети К внутри квадой облвоти В из ¡¡¡¡¡, крома точек» принадлвквщих ИНГ, являются г+-точ1шкш (или г\_-точкед),

' Прибавим ко шшюству МВД1 все узлаеио точки сети Я, лаккцие на вешаниях бавоошс областей первого порядка. Приовоии новое внйчэкав ШГГ рарокзЕдай ШТ£! 1ШТ2 :«ШТ.

Г1-я,итерация. Бавовой облэстью п-го порядке рчнтевм праиэао-лькнй максимальный влэыант на множества 1Ш( областей, ограниченных Я-кршшмл, таких, что воа увлаше точки сети Я внутри квкдой области V на ЧИ1, являются г+-точ::еми (или г_-точквми), -или ловат в Ш£Г.

Прибввда ко шюаюотву 1№ все увловыв точки сети Я, лвиещкв на 'замыканиях бааовых областей п-го порядка. Присвоим новое вначешге МНТ переменной Ш£Гп+11 ( ШГ.

Итеративный процосс продолааетон, пока на останется ни однсй пари (Г),!^» гда Т1 и ¡Г^ - увловыа точки сети К, яалящшэся 'соответственно г+-точкой и г_-точкоа,нэ пр'.шсдлакаадом 12ГГ.

Еудон навивать предбазовой областью любую состоящую из клеток сатк Й подобласть базовой области произвольного порядка на сати И. Границу базовой области назовем базовой кривой.

Определение 6. Будем называть чистыми точками произвольной базовой ( првдоазовой) области п-го порядка ьнутрешме для <4

узловые точки сети í?f не прмнадлзлащиа ИЩ'П_ ¡.

Вамачвниа. Еоли г - бирагулярная ааточиая функция, то вое чиатна точки произвольной базовой (предбвзапой) области одновременно являются г+-точкамн ши г_-точкаьрь -

Определенна 7, Будем навивать положительно определенной базовую (првдбваовую) облеоть Р, если вса ее чиатые■точки являютоя г+-точкв№5, В противном случае будэы навивать ? отрицательно определено® базовой областью.

Теорема I. Коли г - бнрегул.трнвя со точная функция , то

совокупность базовых кривых есть границе точачшгр шог9СТйа * ,, , <<.осли клетка

Г - { (x,¡¡) \r(z,y) Í o },TJ& клетке .

Опрадолекка В. С-точкай Суден 'нашивать узловую точку 1 сети R на прямоугольника П, удовлотрорящув хотя бы одному пз двух условий» (I) Т - грыигшвя точка прямоугольника П| (3) ? - г+-точка, и орзди четырех клеток, длл когорт ? - угловая то то а, хотя бы одна клетка содержит хотя Си одну г_-тач;:у.

Тзорема 2. Иола г - С«»рагуляр!оя функция, то совокушюоть гра ничшх точек платочного »агегэетяз V раьиа о тотлсстьп до уалоши то чек Q5TH Я, лавгвдх на граищ» пржоуголыкаса П кмссестпу С-точзк.

Онрэдэлэнкэ 9. Пазом?! ü-rrp.-ísaf: произвольную Л-криаув гехув( что воэ лоиаирш па це'А уаяогыо точзщ cora Л является С-точка'/а.

Еслк г - ¿^регулярная сеточная функция, то из теорем I а 3 швам: искомая грвпвцв точэчного игсязсгЕО Г есть савокуппооть 503Б й-кришх о зочсастьн до граничим точек прямоугольника П.

Теперь рассмотрим вспроа о поотрсвнга берегулярной соточио" функция, наилучшим ; ь кекотсро« тшЗргляум скаслл ) сЗргзои spz-блккевдгС данную. Еола nao уотракзсот погрешность, :;э прввксвэ-цая длины звона сети й, то, очевидно, могло вез клетки, подарвсцгч хотя Зы.сдау г - течку, пвреспродолттг, с -гу.этка. &-.л втога

ввэдэи ааточную Функция г( на сети R I

1 , аолн Г пршвдпакат котя Си одной к латке сети Я, хотя Си для одной угловой точки которой выполняется! PjWJ-J r(f)>Ol.

О ~ в противном случае. Еоли кем вакнее точность и допустимо удвоенна объема

ваойходаыоЯ пааята для программной реализации расчетов, прибегаем к

1!ык9льч9№ш еде08 свти hi

Ешачания в угловых точках кездой клетки сети Я1, получашюй 'взгтьчаиизы вдвое сети Л, определяем по формула:

ш р1(2*Х+1,2*у+1) » r1(2*x,2*yt1) « - r'f2<jr,£<yj - Г(х,у)

итак, ш ноезн прообразовать произвольную сеточную функцию в Окрагулврную даумя способами! (1) оохрвшш точность воходипх дашшх - - о камальчешюм вдвое растровой сети} (2) о точпоатью до клеток о углошаи точками разных знаков - на исходной с эти Л,

рассмотрим тепзрь, как ровать задачу для регулярной саточной •функции |К которой ка моим привести произвольную Ьаточную функцию на со та Я, цаматт вкачвгая г, как правило, виь на незначительной чзотз узловых точек сэти Я, лоиавщх в расчетном прямоугольнике П.

Ынояэство г+-точэи регулярной функции содаравт, кроне шоЕвстеч г+-точок, npspiaananaiissx г+-клетком, г+-точка, лааваща на изолированных лоиакцх, состоящих из г^-евэньав. ( воамогао, концы втих дошлых леаат ' яа границах некоторых максимальных клеточных тал из г+- клоток или яа границе расчетного прямоугольника П ).

Теорема а, Если г* - регулярная сеточная функция на озти Я, то каадая граничная точка мноваотва У - Г (х,у) | г(х,у) 10) является 0 -точкой (см, теорему I ),

Иа теоремы 3 оразу следует что если г - регулярная сеточнвя

t

функция нш сети Я, то произвольное максимальное множество И непересекающихся попарно в отрогом смноле К-кривых содержит вое граничные точки мнокеотвв V - ( (х| г{х,у) } О Значит, ИХ определяет некоторое измельчение разбиения прямоугольника П на 7 и П\7. Итак, второй вариант схемы влгоритмв Т1г

1. Регуляризация сеточной функции г ( см. п. Й.2.2 )|

2. Выделенкэ максимального мнот:остяп поперэсекэвдшссл попарно В отрогом ОИНСЛЭ Я-КрНВНХ|

3. Получение искомой границы путем аамвиы , кривых, ограничивающих предбазовие области, составляющие какую-либо ба эовую область, отой кривой, огранлчивпщей ия объадоншто.

Для реализации отгй схемы необходимо х (X) Научиться определять, является ли произвольная детая совокупность непересекающихся попарно в отрогом смысла Я-кргсвых максимальной! (2) уметь определять для двух гфоизаолышх лрэдбазовых областей, составляют ли они одну предбвзовую область.

Эти вопросы решаются с помощью следующих теорем»

Теорема 4. Если в процесса выполнения алгоритма Р1 осталась С-точска, принадлежащая некоторой г+-клотк9, из лежащая па объединении выделенных И-кривых, то необходимо существует *-криввя, непересекающаяся в строгом смысла ни с одной из выделенных И-кривых.

Обратное утаерткдение неверно. Но, во всяком случае, если все С-точки лежат на объединении выделенных ¿(-кривых, то совокупность выделенных ^-кривых определяет некоторое измельчение розбиоил расчетного прямоугольника П па точечные множества У и П\7, где V - ( (х,у) \г(х,у) 10).

• Теорема 6. Если г - регулярная функция, то две предбвэовые области А и В составляют одну лрэдбааовую область в том и только

том случае, ооли выполняется одно иг двух условий! ( I) Обе продбявовыэ облвоти Л Я В положительно определены, и их границы пересекаются хотя бы по одному звену сети Я| (й). Обе предбавовые области Л к В отрицательно определены, и юс границы пересекаются по некоторому шВеству звеньев сети Я ,ие оодеряащему ни одной пари соседних горивонталышх или соседних вертикальных звеньев сети Я, не принадлежащих клеткам.

В П. 1.3 главы I рассматривается вопрос о выборе плотности ею овти веданных точек в случае дискретного определения расчетных функций.

В п. 1.4 главы I предлагвэтся описание и теоретическое обоснование алгоритмов LOGIC, LOGIC 1, 1CGI02 определения принадлежности произвольной точки плоскости П соответственно односвязной области, многосвязному точечному множеству, произвольному логическому вырежеюго от многосвязных точечных множаотв, лежащих на плоскости П . При втом анализируемые точечные множества ограничены многоугольниками и задан« ориентированными компонентами связности границ.

Главн 2 и 3. Излагаются принципы • программной реализации блоков и AOCUE алгоритма FAST.

Глава 4. Алгоритмы уточнения корней трансцендентных функций.

Предлагается описышо алгоритмов DIXO, DIX01, 1)1X02 уточнения корней на прямой и двумерной плоскости класса алгоритмов последовательного сжатия поискового пространства методом ветвей и границ. Они сходятся независимо от поведения расчетных функций вблизи действительных коркой. Новизна алгоритмов - в независимости их точности от кратности искомых корней! в случае DIX01 и DIX02 - в вкономии времени счета благодаря приему "отслекивения" корней при переходе на сосодниэ горизонтали при обработке координатных

горизонт лэ ft, лвнкцет п расуэтном терсллэлэтзида, в порядке возраотвияя та срдтгнот.

Î2S3âJb Алгорягк F.XTH ропэтя o:?orerei ?рл:оцэцдеитнчя

урвгаюпкЗ.

Пусть глася СКОТ01ЧГ s п грсяодзядвкхтж урпвпогай с fj(z)«o }jm1 п от m-кэрпой n?icíopreo."t яорэгашюЯ з> >п rta п-г/пркои

кубе Р J Б я-кэркоа дотзртовой IMQCK00T3 rt* ДЛЯ провозояьшх натурплькшс тип , гдэ - ¡гвпрэрцккга функция im Pj.

Алгоритм FSTÜ ГОД. эяяот "гитатки" корки ohcïw&î 5 о ТОЧНОСТЬЮ до f/fffe/1');, глэ ,?51'0прэдэлаэтсг! KEnfí-tMbítO» соамоянеИ ПОГрййОЮОТЫВ ШОДШШЯ* ''Гг0 ""P"" " ^буЗГОЗ pnCÍSTOS 15

П'ЛИОЛЯЭТСП nporpcwnîo R проЦЗООЭ ЕаДвЛЭЯГСЯ корма. ШЯ роясот отстану yposirairSí Я о aüttu с адапютзатам возмоги:« етюм

окибош rsopiPî oïOCTtrj S, л^г-^гт-а а доотэгочпо ausaa кубах, из гряяацзх каторг,гх готя Си ккго7от*19 Сузжпя ко стгхзатэа ( jj(-t) }J=1,n ) врязжд-те Bssçftirra о."кго опэкз, »згу? быть логэряз». Пзвнзыз 31ГН - той» что врз про:гзоолькса структура кнояэогвя ггср:;з ciiotewi а возздажа «-згах чаотя* oîîctvvj в рзсчвстоа облети: вдгоратк KÏ2ÏÏ кояэчэа lí огогкп-щ п док:о2 аптоцягетсдо рмтатоз, а тиша в гаояшм сопользсг.з'.г-п овэраяета« плата ЗЕЧ. OckoekoS пвдоотагок - гагоэтжзкооп. гГсяогьэопгапя. квсодав изярзилэваого поиска ítopsBíí.

ÖKSiLib Алгоритм sacsïi рястрачаго тазгкза тсготел:

а кгюгокэрпа вроотрглотзвг»

Предязгмтоз алгоритм й?.СГТХ кглйтеразецгг гоктсрпс/го

(аюкесгва сеч rrpv.^-P^-s.ткгего iSr.'îi-r^ дст rruracrsfm гычсп 1«шш;гпасг!„ '¡.лгсргга 31СГТП пгр'эттач ,",лл -tsaccrsjüff.rj';! D проотрзиотззг тачгогяашап кк&сгро^шпгк зуаэцжоэ; ^атс&та» п 1шог'с:.»эршх apoorpsaoi'cax о сушоггсжо кзпзягЗгзхя з^з^ч, з

шага (фа наличия классификационных параметров внсодах шшштуд. огрвкичеии» ци пршенедае алгоритма САСШТ11 цообходико наличие априорно взвэотного признака высокое инфорнатгоздоотв.

£АСЕ?1 рниодош)?»

(1) рашдароэвняэ рлааанфвкацнощадх признаков да принято»? в пв'лаоптолоПй? критерии щйорэдтдедости , устой^пнюму в (аюгокорк^ пространствах при сущестранной нолинвйлостн связей ыз:зду клЕРопфиквщгашшма пртиекавд;

(2) РааОввша юшсокфшруерго множестве И на плоскости НИ, 'наткнутой на £ седа иыформатавшх признаков, где К - варанав

вадашюа число. Реадаэувтая путем паоладоватолышго дроблашш цнеюсгва и на "агустки" точек в дауызрццх гиперплоскостях плоскости' ¿'¿', При ктоа рьаулдарущаз рааеиаша удовлетворяет априорно аадшшому уалооик, для определения которого в программной , росллсацта 2АС2Т1 шдзлон слоциалышй модуль.

Г^ага 7. ОлтЕдаЕцкя лдайдой векторной функции по

рашцроцанаам критериям к матрице оошаоткости на полиэдра.

Предлагается сГшоещю алгоритма ЩИЕРАЛ. 0;; сптишвнрувт лздгэйцгю векторную фупнцшз п пврэизшшх по набору п ренкф0ва£вшг; аддитивных 1.-раторзэв, гда в ,п - 2,3,... прл ! Еркггсолышх ограничениях на вектор перэюэтшх. Время счета прсгрвкйшй роалазицш слгьритвд ШНЕРАЛ лкюйио пропорционально в В п> Па алгоритму 1Д!КШЛ раелизоааца и апробирована в | Гвсшшачаских расчетах методика 01РЯ пероочета воцестшашюга состава геологических оОразцов на катаральный. Предлагаемая реаливация отличается от общепринятой легкостью изменения списков расчетных окролов и минералов, ООеспечена возможность применения алгоритма МИНЕРАЛ для апробации новых расчетных методик, .-.основанных на линейных преобразованиях переменных . При втоы

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

Осногоме результат» работа. Разработаш, теоретически обоснованы и реализованы па 5БМ алгоритма FAST, EXTR, DIXO, DIX01, ЫХ02, вычисления корнай трансцендентных ypamtamift методам« растрового анализа и стратегии вэтпвй и границ на отрезке,конечно связном плоском мнокеотве, параллелепипеде многомерного пространства. Алгоритмы сходятся при произвольных расчетных функциях и топологических характеристиках искомых, точаЧ1ШХ мно«вств и кривых. Они не нуждаются п предварительном анализа данных. FAST выделяет ориентированные границы плоских конечно связных множеств по произвольным вычислим»®! ограничениям и представляет выходную информацию в форме, удобной для дальнейшей обработки па ЭВМ .

Разработан и реализовен на ЭВМ алгоритм ФАСЕТ1 разбиения точечных множеств на кластеры в многомерных пространствах каялеот-вешшх и качественных ранкировянннх признаков, устойчивых при оуще-отввнно нелинейных связях мявду признаками и виоокЬй размерности пространства признаков. Сформулирован в терминах оптимизационных задач клаос геохимических методик пересчета. Предлагается программ пая реализация методики CIVH нормативного пересчета веце ствегагаго состава геологических образцов на минеральный, позволяющая модифицировать пересчет без изменения расчетной схема.

Основные результаты диссертации опубликованы в следуй^ работах!

1. Гутман Т. Д. Ускоренный метод выделения границ плоских яордано-вых областей о конвчносвяпными границами. Твзйон докладов первой республиканской конференций молодых ученых! БФАН СССР, 1'98Б. о. ЗБ.

2. О некоторых приемах автоматизации моделирования процессов на ЭВМ // Микроэлементы в магматических и рудшх формациях Урала. -

Уфа, Н5АН СССР, I9B7. с, 40-46.

3. Гутыая Т.Д. Несколько алгоритмов растрового анализа при обработке геохимических данных на ЭШ. Препринт / Е31Ц УРО АН СССР, У$а, I9S0. 26 с.

4. Гутман Т.Д. Один алгоритм растрового анализа при классификации геологических объектов на ЭШ /ин-т гоол, УРО АН СССР. -Уфа, 1990, 13 с,:ил. библиогр. 3 назв. рук. деп. в ВИНИТИ 29.05.90 »Р2942-В90.

5. Гутман Т.Д. О некоторых приемах растрового анализа при обработке геохимических данных на ЭШ, // Минералогии, геохимия и полезные ископаемые Урала.-Уфа,. ШЦ УРО АН СССР, 1991. с. 122-127.

6. Гутиап Т.Д. Алгоритм преоразованил геохимических данных на прямоугольном растре и декартовой плоскости. // Микроэлементы в магматических и рудных формациях Урала, - Уфа! ЮАН СССР 1992. с. I22-T27.

7. Гутман Т.Д., Курыангалеева А.Ф., Ахмадеева Ф.Н.О фасет.ировании точечных множеств баз предварительного обучения // Тезисы докладов конференции "Математическое про гримирование и приложения". Свердловск. УРО АН СССР. 1991 г.

8. Геометризация залежей сложной формы на SB's // Отчет 17-79 кафедры ТМГМ Башгосуниверситета "Разработка способов Повышения пффеи-тивности использования запасов нефти и газа в сложнопостроенных залежах Западной Сибири. Глава 2. IS80 г.

Зек.141,тир.100, ротапринт Башк.ун-та