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

doctoral thesis

• Title (english): Deepest descent method for efficient numerical solving of polynomial systems
• Author: Ivo Beroš
• Mentor: Nikica Hlupić (mentor)
• Committee member: Nikica Hlupić (član povjerenstva)
• Granter: University of Zagreb; Faculty of Electrical Engineering and Computing; (Department of Applied Computing); Zagreb
• Defense date and country: 2020, Croatia
• Scientific / art field, discipline and subdiscipline: TECHNICAL SCIENCES; Computing
• Universal decimal classification (UDC): 004 - Computer science and technology. Computing. Data processing

Abstract

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.

Abstract (english)

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.

• Keywords: polinomni sustav; metoda najdubljega spusta; numeričke metode
• Keywords (english): Rad ne sadrži ključne riječi na drugom jeziku.
• Language: croatian
• URN:NBN: urn:nbn:hr:168:683771
• Study programme: Title: Computer Science; Study programme type: university; Study level: postgraduate; Academic / professional title: Doktor znanosti (Doktor znanosti)
• Catalog URL: http://lib.fer.hr/cgi-bin/koha/opac-detail.pl?biblionumber=52600
• Type of resource: Text
• Extent: xii, 175 str.
• File origin: Born digital
• Access conditions: Open access
• Created on: 2022-03-15 08:15:24