Java - algoritmy hľadania nulových miest

Základy informatiky - jazyk Java

---

---

Platforma Java - prehľad

Úvod do programovania v jazyku Java

Java - objektovo orientovaný prístup

Vzorové príklady:

Prvé programy v Jave

Vzorové triedy v Jave

Java applety

Java - desktopové aplikácie

Java - implementácia numerických algoritmov

>Java - algoritmy hľadania nulových miest
>Java - algoritmy numerického derivovania
>Java - algoritmy numerického integrovania
>Java - algoritmy aproximácie
>Java - algoritmy interpolácie

Java - triedy geometrických tvarov

Pokročilé témy:

Základy práce s NetBeans IDE a vývoj modulov

Algoritmy hľadania nulových miest (A root-finding algorithms), sú také algoritmy ktoré hľadajú takú hodnotu x, pre ktorú platí f(x)=0, pre danú funkcie f.

Hľadanie nulových miest rovnice [math]f(x) − g(x) = 0[/math] je totožné s riešením rovnice [math]f(x) = g(x)[/math], kde x je neznáma. Inak povedané, ľubovoľnú rovnicu môžeme vyjadriť v kanonickom tvare [math]f(x) = 0[/math], takže riešenie takejto rovnice je vlastne hľadaním nulového bodu funkcie. Prvý odhad riešenia rovnice je počiatočný návrh. Zvolená metóda (algoritmus) vypočítava postupnosť hodnôt, ktoré berú v ohľad predchádzajúcu vypočítanú hodnotu a riešenú funkciu f.

Newtonova metóda nulových miest

Pre danú funkciu [math]f(x)[/math] a je algoritmus definovaný pomocou vzorca

[math]x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}. \,\![/math]

kde

[math]{f'(x_n)}. \,\![/math] je prvá derivácia funkcie [math]{f(x_n)}. \,\![/math]

Hodnota [math]x_0[/math] je prvý odhad riešenia. Výpočet skončíme vtedy, keď sa hodnota [math]{f(x_n)}. \,\![/math] blíži k nule.

Podrobnejšie o Newtonovom algoritme hľadania nulových miest je v článku Algoritmy hľadania nulových miest#Newtonova metóda nulových miest

Metóda polenia intervalov

Podrobnejšie o algoritme polenia intervalu je v článku Algoritmy hľadania nulových miest#Metóda polenia intervalov

Riešenie v jave

V tejto časti budeme pokračovať v aplikácii, ktorú sme si navehli v časti Java (Swing) - práca s vizuálnymi komponentami#Práca so záložkami. Prvú záložky pomenujeme 'Nulové miesta' a vložíme na ňu nasledujúce komponenty:

• jButtonGroup - dovolí výber len jednej možnosti
  • názov komponentu: skupinaNuloveBody
• jRadioButton - možnosť výberu Newtonovej metódy výpočtu nulového miesta.
  • názov komponentu: rbNewton
  • Text komponentu: 'Newtonova m.'
  • vlastnosť selected: true
  • vlastnosť buttonGroup: skupinaNuloveBody
• jRadioButton - možnosť výberu metódy polenia intervalu pre výpočet nulového miesta.
  • názov komponentu: rbPolenie
  • Text komponentu: 'Newtonova m.'
  • vlastnosť buttonGroup: skupinaNuloveBody
• jTextField - textové políčko pre vloženie odhadu riešenie pri Newtonovej metóde
  • Názov kompoentu: textOdhadX
  • Text komponentu: '0'
• jTextField - textové políčko pre vloženie bodu A pri metóde polenia intervalu
  • Názov kompoentu: textPolenieA
  • Text komponentu: '-1'
• jTextField - textové políčko pre vloženie bodu B pri metóde polenia intervalu
  • Názov kompoentu: textPolenieB
  • Text komponentu: '1'
• jlabel - texttový objekt, do ktorého vpíšeme výsledok riešenia
  • Názov kompoentu: labelX0
  • Text komponentu: 'x0=...'
• jButton - tlačidlo pre spustenie algoritmu výpočtu nulových bodov.
  • Názov kompoentu: tlcNula
  • Text komponentu: 'pocitaj!'

Návrh dizajnu aplikácie pre výpočet nulových miest.

Úprava triedy Function.java

Nevýhodou newtonovej metódy je fakt, že potrebuje mať k dispozícii prvú deriváciu funkcie pre ktorú hľadnáme nulový bod. Doplňme teda do triedy Function.java metódu derivacia:

public class Function {

    private double a, b, c;

    // vsetky ostatne metody su uvedene v predchadzajucom texte

    public double hodnota(double x) {
        return a * Math.cos(b * x) - Math.pow(x, c);
    }

    public double derivacia(double x) {
        return -a * b * Math.sin(b * x) - c * Math.pow(x, c - 1);
    }
}

Úprava triedy Solver.java

Do triedy doplníme 2 nové metody, ktoré budú implementovať 2 numerické algoritmy hľadania nulových miest.

Newtonova metóda nulových miest

Túto metódu budeme implementovať pomocou rekurizie. Rekurzia je vysvetľovaná v článku Rekurzia.

Metóda polenia intervalov

V článku Algoritmy hľadania nulových miest#Metóda polenia intervalov je uvedený zdrojový kód v jazyku C. Tento zdrojový kód je na 95% podobý zdrojovému kódu v Jave. Preto použijeme tento zdrojový kód a upravíme ho do syntaxe jazyka Java.

V nasledujúcom výpise sú uvedené len nové metódy triedy Solver:

package numeric;

public class Solver {

    private Function f;
    private double presnost;

    public double nulaNewton(double x0) {
        if (Math.abs(this.f.hodnota(x0)) < this.presnost) {
            return x0;
        } else {
            return nulaNewton(x0 - f.hodnota(x0) / f.derivacia(x0));
        }
    }

    public double nulaPolenie(double a, double b) {
        // predpoklad správneho riesenia:
        // jedna z hodnot f(a),f(b) musi byt mensia ako 0, druha vacsia ako 0
        double lo, hi, mid;
        if (this.f.hodnota(a) <= 0) {
            lo = a;
            hi = b;
        } else {
            lo = b;
            hi = a;
        }
        mid = lo + (hi - lo) / 2;
        while ((mid != lo) && (mid != hi)) {
            if (this.f.hodnota(mid) <= 0) {
                lo = mid;
            } else {
                hi = mid;
            }
            mid = lo + (hi - lo) / 2;
        }
        return mid;
    }
}

Použitie algoritmov v programe

Komponentu tlcNula pridáme udalosť actionPerformed, v ktorej bude výpočet nulového miesta pre funkciu definovanú v triede Function.

    private void tlcNulaActionPerformed(java.awt.event.ActionEvent evt) {
        double h1=0,h2 = 0;
        if(rbNewton.isSelected()){
            h1=Double.valueOf(textOdhadX.getText());
            h1=s.nulaNewton(h1);
        }
        if(rbPolenie.isSelected()){
            h1=Double.valueOf(textPolenieA.getText());
            h2=Double.valueOf(textPolenieB.getText());
            h1=s.nulaPolenie(h1, h2);
        }
        labelX0.setText(String.valueOf(h1));
    }

Poznámky k zdrojovému kódu:

• Newtonova metóda potrebuje odhad správneho riešenia:
  • túto hodnotu získame z komponentu textOdhadX a uložíme ju do premennej h1.
  • do premennej h1 uložíme výsledok, ktorý nám vráti metóda nulaNewton
• Metóda polenia intervalu potrebuje 2 hodnoty: bod v ktorom má funkcia zápornú hodnotu a bod v ktorom má kladnú hodnotu
  • tieto hodnoty získame z komponentov textPolenieA a textPolenieB. Hodnoty uložíme do premenných h1 a h2.
  • do premennej h1 uložíme výsledok, ktorý nám vráti metóda nulaPolenie
• výsledok vypíšeme do komponentu labelX0.

Na nasledujúcom obrázku je funkcia f(x)= 1*cos(2*x)-x^2, zobrazená na intervale <-5, 5>. Toto zodpovedá zápisu v konštrukture triede kiwikiApp (naša plikácia):

    public kiwikiDemo_graf() {
        initComponents();
        f = new Function(1,2,2);
        t = new Transform(panel.getWidth(), panel.getHeight(), 5);
        s=new Solver(f,0.000001);
    }

Ukážka funkčnosti:

Aplikácia algoritmov hľadania nulových miest.

Vylepšenie funkcionality:

Do aplikácie doplníme vizuálne znázornenie riešenia. Nájdené riešenie znázorníme ako modrý krúžok.

Riešenie je jednoduché. Stačí doplniť vykreslenie kruhu na súradnice [x0,0], resp. v našom prípade [h1,0].

    private void tlcNulaActionPerformed(java.awt.event.ActionEvent evt) {
        double h1=0,h2 = 0;
        if(rbNewton.isSelected()){
            h1=Double.valueOf(textOdhadX.getText());
            h1=s.nulaNewton(h1);
        }
        if(rbPolenie.isSelected()){
            h1=Double.valueOf(textPolenieA.getText());
            h2=Double.valueOf(textPolenieB.getText());
            h1=s.nulaPolenie(h1, h2);
        }
        labelX0.setText(String.valueOf(h1));
        int r = 3;
        g.setColor(Color.blue);
        g.drawOval(t.getX(h1)-r, t.getY(0)-r, 2*r, 2*r);
    }

Aplikácia algoritmov hľadania nulových miest - znázornenie riešenia