Metoda najdubljega spusta za brzo numeričko rješavanje polinomnih sustava

disertacija

• Naslov (engleski): Deepest descent method for efficient numerical solving of polynomial systems
• Autor: Ivo Beroš
• Mentor: Nikica Hlupić (mentor)
• Član povjerenstva: Nikica Hlupić (član povjerenstva)
• Ustanova koja je dodijelila akademski / stručni stupanj: Sveučilište u Zagrebu; Fakultet elektrotehnike i računarstva; (Zavod za primijenjeno računarstvo); Zagreb
• Datum i država obrane: 2020, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: TEHNIČKE ZNANOSTI; Računarstvo
• Univerzalna decimalna klasifikacija (UDC): 004 - Računalna znanost i tehnologija. Računalstvo. Obrada podataka

Sažetak

Tema ovog rada je primjena metoda najdubljeg spusta na rješavanje polinomnih sustava. Metode najdubljeg spusta su iterativne metode u kojima se sljedeća iteracija određuje kao točka na pravcu spusta na kojem zadana norma dostiže najmanju vrijednost. Metode se razlikuju prema odabiru smjera spusta i norme. Kao norma se obično koristi euklidska, a u ovom radu je analizirana i primjena max-norme. U radu su opisane različiti načini odabira smjera spusta. Osim standardnih smjerova spusta (Newtonov smjer, smjer najstrmijeg spusta), razmatrani su i Gauss-Seidelov način odabira smjera spusta, korištenje smjera koordinatnih osi, kao i odabir smjera spusta rješavanjem problema linearnog programiranja. Za uspoređivanje metoda proveden je numerički eksperiment čiji je cilj bio utvrditi uspješnost metoda. Testiranje je provedeno na kolekciji od više od 100 polinomnih sustava različitih dimenzija prikupljenih iz relevantnih izvora. Uspješnost metode za određeni problem je definirana kao postotak iterativnih postupaka koji su započeli s početnom točkom iz unaprijed zadanog skupa početnih točaka, a konvergirali su rješenju problema. Na temelju uspješnosti metoda, formirana su tri indeksa pomoću kojih su uspoređene metode. Metode su uspoređene međusobno i s dva referentna algoritma, MinPack i NLEQ. Eksperiment je pokazao da je većina metoda najdubljega spusta uspješnija od referentnih algoritama. Glavni doprinos rada je što je pokazano da se metode najdubljeg spusta mogu uspješno koristiti za brzo i efikasno rješavanje polinomnih sustava.

Sažetak (engleski)

This thesis deals with the deepest descent methods applied on solving polynomials. The deepest descent methods are iterative methods in which new iteration point is the global minimizer of the chosen norm along the search direction. The methods differ with respect to the choice of the search direction and norm. Although the common choice of the norm is the Euclidean norm, the use of the max-norm is analysed in the thesis as well. The search direction can be any standard direction such as Newton direction, the steepest descent direction, the coordinate axes, or a combination of standard search directions. Furthermore, two new search directions are analysed: the Gauss-Seidel direction and the LP direction, which an A numerical experiment was performed to compare the methods’ performance. First, a collection of more than a100 polynomial systems from the relevant sources was compiled. Then, the success rate for each method and problem was calculated, whereby success rate was defined as the percentage of the convergent iteration processes which start with the initial point from any set S. The three indices, based on the success rate, were used for the comparison of the methods. The deepest descent methods were compared with two benchmark methods, the MinPack and the NLEQ, and the results suggest that nearly all the deepest descent methods had a better success rate than the benchmark methods. The research conducted in this thesis has shown that the deepest descent methods can be successfully used for fast and efficient solving of the polynomial systems which is consequently its main contribution to science.

• Ključne riječi: polinomni sustav; metoda najdubljega spusta; numeričke metode
• Ključne riječi (engleski): Rad ne sadrži ključne riječi na drugom jeziku.
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:168:683771
• Studijski program: Naziv: Računarstvo; Vrsta studija: sveučilišni; Stupanj studija: poslijediplomski znanstveni (doktorski); Akademski / stručni naziv: Doktor znanosti (dr. sc.)
• URL zapisa u katalogu: http://lib.fer.hr/cgi-bin/koha/opac-detail.pl?biblionumber=52600
• Vrsta resursa: Tekst
• Opseg: xii, 175 str.
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Otvoreni pristup
• Datum i vrijeme pohrane: 2022-03-15 08:15:24