Das Newton-Verfahren

Aus ProgrammingWiki

< Grundlagen der funktionsorientierten Programmierung mit SCHEME

Archivierte Version vom 2014-07-14T07:03:11+00:00. Aktuelle Version

Autor: Schneider, Tim

Grundlagen

Zur näherungsweisen Bestimmung der Nullstelle einer stetigen Funktion f kann an einer beliebigen Stelle x die Tangente angelegt werden. Für den Anstieg m der Tangente gilt:

m = \frac{f(x)}{x-x_0}

wobei x_0 die Nullstelle der Tangente ist. Diese Nullstelle ist ein erster Näherungswert für die Nullstelle der Funktion f und wird als Startwert für die erneute Anwendung des Verfahrens genutzt. Damit kann die Nullstelle der Funktion f mit beliebiger Genauigkeit angenähert werden.

Implementation

Zur Bestimmung des Anstiegs m nutzen wir die bekannte Prozedur ableitung (s. Prozeduren höherer Ordnung (II)).
Natürlich müssen wir auch daran denken, dass die stetige Funktion f u. U. keine reelle Nullstelle besitzt.

(define h 1e-10)
(define eps 1e-06)

(define ableitung
  (lambda (fkt)
    (lambda (x)
      (/ (- (fkt (+ x h)) (fkt x)) h))))

(define nst
  (lambda (fkt x)
    (letrec ([max 10]
             [suchen
              (lambda (x n)
                (cond
                  [(< n 1) #f]
                  [(< (abs (fkt x)) eps) x]
                  [else
                   (suchen (- x (/ (fkt x) ((ableitung fkt) x))) (- n 1))]))])
      (suchen x max))))

(nst (lambda (x) (- (sqr x) 2)) 10)

Nullstellensuche und Schaubild

Wir wollen das Ergebnis der Nullstellensuche am Schaubild der Funktion überprüfen.

(define nr 1)
(define genau 6)
(define breite 610)
(define hoehe 460)
(define rand 50)
(define canvas (eval (string->symbol (string-append "canvas" (number->string nr)))))
(define raster #f)
(define bez "x")

(define black
  (lambda (canvas)
    (setcolor canvas 0 0 0)))

(define red
  (lambda (canvas)
    (setcolor canvas 255 0 0)))

(define brown
  (lambda (canvas)
    (setcolor canvas 100 50 0)))

(define orange
  (lambda (canvas)
    (setcolor canvas 255 100 0)))

(define yellow
  (lambda (canvas)
    (setcolor canvas 255 200 0)))

(define green
  (lambda (canvas)
    (setcolor canvas 0 255 0)))

(define blue
  (lambda (canvas)
    (setcolor canvas 0 0 255)))

(define pink
  (lambda (canvas)
    (setcolor canvas 200 50 200)))

(define n-tes-mod
  (lambda (ls anz)
    (list-ref ls (modulo anz (length ls)))))

(define genaurunden
  (lambda (x anz)
    (let ([n 0] [erg 0])
      (if (not (= x 0))
          (set! n (inexact->exact (round (- anz (/ (log (abs x)) (log  10)) -0.5)))))
      (set! erg (/ (round (* x (expt 10 n))) (expt 10 n)))
      (if (integer? erg)
          (inexact->exact erg)
          (exact->inexact erg)))))

(define groessenordnung
  (lambda (x)
    (if (= x 0)
        1
        (let ([pot (/ (log (abs x)) (log 10))])
          (genaurunden (expt 10 (floor pot)) genau)))))

(define minimum
  (lambda (x y)
    (if (< x y) x y)))

(define maximum
  (lambda (x y)
    (if (> x y) x y)))

(define ungleich-null
  (lambda (x y)
    (if (= x y 0) (+ y 1) y)))

(define schaubild
  (lambda (fkt-list x1 x2 y1 y2 von bis koordcolor color-list)
    (clear canvas)
    (setwidth canvas 1)
    (let* ([textgroesse 9]
           [rand 50]
           [xu (exact->inexact (minimum x1 x2))] [xo (exact->inexact (maximum x1 x2))] [xo (ungleich-null xu xo)]
           [yu (exact->inexact (minimum y1 y2))] [yo (exact->inexact (maximum y1 y2))] [yo (ungleich-null yu yo)]
           [spmin rand] [spmax (- breite rand)] [spend (+ spmax 15)]
           [zemin (- hoehe rand)] [zemax rand] [zeend (- zemax 15)]
           [s00 (+ (* (/ (- xu) (- xo xu)) (- spmax spmin)) spmin)] [s0 s00]
           [z00 (+ (* (/ (- yu) (- yo yu)) (- zemax zemin)) zemin)] [z0 z00]
           [spvon (+ (* (/ (- von xu) (- xo xu)) (- spmax spmin)) spmin)]
           [spbis (+ (* (/ (- bis xu) (- xo xu)) (- spmax spmin)) spmin)]
           [mx (- xo xu)] [teilerx 1] [stepx (/ (- spmax spmin) mx teilerx)] [ex mx] [faktorx 1]
           [my (- yo yu)] [teilery 1] [stepy (/ (- zemin zemax) my teilery)] [ey my] [faktory 1])
      (letrec
          ([anpassen
            (lambda (m)
              (if (> m 2)
                  (if (<= m 20)
                      m
                      (anpassen (/ m 10)))
                  (if (> m 2)
                      m
                      (anpassen (* m 10)))))]
           [teilen
            (lambda (m)
              (cond
                [(< m 3) 5]
                [(< m 10) 2]
                [else 1]))]
           [x-raster
            (lambda (sx zy)
              (if (> zy (- zemax 1))
                  (begin
                    (if (and (< zy (+ zemin 1)) (> (abs (- zy z0)) 1)) (line canvas sx zy sx zy))
                    (x-raster sx (- zy 3)))))]
           [x-teilen-positiv
            (lambda (sx)
              (if (< sx (+ spmax 1))
                  (begin
                    (if (and (> sx (- spmin 1)) (> (abs (- sx s0)) 1)) 
                        (begin
                          (line canvas sx z0 sx (- z0 3))
                          (if raster (x-raster sx zemin))))
                    (x-teilen-positiv (+ sx stepx)))))]
           [x-teilen-negativ
            (lambda (sx)
              (if (> sx (- spmin 1))
                  (begin
                    (if (and (< sx (+ spmax 1)) (> (abs (- sx s0)) 1)) 
                        (begin
                          (line canvas sx z0 sx (- z0 3))
                          (if raster (x-raster sx zemin))))
                    (x-teilen-negativ (- sx stepx)))))]
           [y-raster
            (lambda (sx zy)
              (if (< sx (+ spmax 1))
                  (begin
                    (if (and (> sx (- spmin 1)) (> (abs (- sx s0)) 1)) (line canvas sx zy sx zy))
                    (y-raster (+ sx 3) zy))))]
           [y-teilen-positiv
            (lambda (zy)
              (if (> zy (- zemax 1))
                  (begin
                    (if (and (< zy (+ zemin 1)) (> (abs (- zy z0)) 1)) 
                        (begin
                          (line canvas s0 zy (+ s0 3) zy)
                          (if raster (y-raster spmin zy))))
                    (y-teilen-positiv (- zy stepy)))))]
           [y-teilen-negativ
            (lambda (zy)
              (if (< zy (+ zemin 1))
                  (begin
                    (if (and (> zy (- zemax 1)) (> (abs (- zy z0)) 1)) 
                        (begin
                          (line canvas s0 zy (+ s0 3) zy)
                          (if raster (y-raster spmin zy))))
                    (y-teilen-negativ (+ zy stepy)))))]
           [faktor
            (lambda (len step)
              (if (<= len step)
                  1
                  (+ 1 (faktor (- len step) step))))]
           [textwidth
            (lambda (str)
              (* textgroesse (string-length str)))]                       
           [textout-widthcenter
            (lambda (sx zy str unten)
              (if unten
                  (if (integer? (string->number str))
                      (text canvas (- sx (/ (textwidth str) 2)) 
                            (+ zy (/ textgroesse 2/3)) str textgroesse)
                      (text canvas (- sx (/ (textwidth str) 2) (- (/ textgroesse 2))) 
                            (+ zy (/ textgroesse 2/3)) str textgroesse))
                  (if (integer? (string->number str))
                      (text canvas (- sx (/ (textwidth str) 2)) 
                            (- zy textgroesse) str textgroesse)
                      (text canvas (- sx (/ (textwidth str) 2) (- (/ textgroesse 2))) 
                            (- zy textgroesse) str textgroesse))))]
           [textout-heightcenter
            (lambda (sx zy str links)
              (if links
                  (if (integer? (string->number str))
                      (text canvas (- sx (textwidth str) 2) 
                            (+ zy (/ textgroesse 2)) str textgroesse)
                      (text canvas (- sx (textwidth str) (- (/ textgroesse 2))) 
                            (+ zy (/ textgroesse 2)) str textgroesse))
                  (if (integer? (string->number str))
                      (text canvas (+ sx textgroesse) 
                            (+ zy (/ textgroesse 2)) str textgroesse)
                      (text canvas (+ sx textgroesse)
                            (+ zy (/ textgroesse 2)) str textgroesse))))]
           [textout-bez-widthcenter
            (lambda (sx zy str)
              (text canvas (- sx (/ (textwidth str) 4)) 
                    (- zy textgroesse) str textgroesse))]
           [textout-bez-heightcenter
            (lambda (sx zy str)
              (text canvas (+ sx (/ textgroesse 2))
                    (+ zy (/ textgroesse 2)) str textgroesse))]
           [x-bezeichnen-positiv
            (lambda (sx e unten)
              (if (< sx (+ spmax 1))
                  (begin
                    (if (and (> sx (- spmin 1)) (> (abs (- sx s0)) 1))
                        (textout-widthcenter sx z0 (number->string (genaurunden e genau)) unten))
                    (x-bezeichnen-positiv (+ sx (* stepx faktorx)) (+ e (* ex faktorx)) unten))))]
           [x-bezeichnen-negativ
            (lambda (sx e unten)
              (if (> sx (- spmin 1))
                  (begin
                    (if (and (< sx (+ spmax 1)) (> (abs (- sx s0)) 1))
                        (textout-widthcenter sx z0 (number->string (genaurunden e genau)) unten))
                    (x-bezeichnen-negativ (- sx (* stepx faktorx)) (- e (* ex faktorx)) unten))))]
           [y-bezeichnen-positiv
            (lambda (zy e links)
              (if (> zy (- zemax 1))
                  (begin
                    (if (and (< zy (+ zemin 1)) (> (abs (- zy z0)) 1))
                        (textout-heightcenter s0 zy (number->string (genaurunden e genau)) links))
                    (y-bezeichnen-positiv (- zy (* stepy faktory)) (+ e (* ey faktory)) links))))]
           [y-bezeichnen-negativ
            (lambda (zy e links)
              (if (< zy (+ zemin 1))
                  (begin
                    (if (and (> zy (- zemax 1)) (> (abs (- zy z0)) 1))
                        (textout-heightcenter s0 zy (number->string (genaurunden e genau)) links))
                    (y-bezeichnen-negativ (+ zy (* stepy faktory)) (- e (* ey faktory)) links))))]
           [x-achse-bezeichnen
            (lambda (str)
              (textout-bez-heightcenter spend z0 str))]
           [y-achse-bezeichnen
            (lambda (str)
              (let ([y-str (string-append "f(" str ")")])
                (textout-bez-widthcenter s0 zeend y-str)))]
           [graph-startpkt
            (lambda (fkt pkt)
              (let ([sx (car pkt)] [zy (cdr pkt)])
                (if (< sx (+ spbis 1))
                    (with-failure-continuation
                     (lambda (error-record error-k) (graph-startpkt fkt (cons (+ sx 1) zy)))
                     (lambda ()                    
                       (let* ([x (+ (* (/ (- sx spmin) (- spmax spmin)) (- xo xu)) xu)] [y (fkt x)])
                         (if (real? y)
                             (begin
                               (set! zy (+ (* (/ (- y yu) (- yo yu)) (- zemax zemin)) zemin))
                               (if (> zy zemin) (set! zy zemin))
                               (if (< zy zemax) (set! zy zemax))
                               (cons sx zy))
                             (graph-startpkt fkt (cons (+ sx 1) zy))))))
                    (cons sx zy))))]
           [graph-zeichnen
            (lambda (fkt pkt)
              (let ([sx (car pkt)] [zy (cdr pkt)])
                (if (< sx (+ spbis 1))
                    (with-failure-continuation
                     (lambda (error-record error-k) 
                       (graph-zeichnen fkt (graph-startpkt fkt (cons (+ sx 1) zy))))
                     (lambda ()
                       (let* ([sx-neu (+ sx 1)] 
                              [x (+ (* (/ (- sx-neu spmin) (- spmax spmin)) (- xo xu)) xu)] [y (fkt x)])
                         (if (real? y)
                             (let ([zy-neu (+ (* (/ (- y yu) (- yo yu)) (- zemax zemin)) zemin)])
                               (if (> zy-neu zemin) (set! zy-neu zemin))
                               (if (< zy-neu zemax) (set! zy-neu zemax))
                               (if (and (< zy zemin) (> zy zemax) (< zy-neu zemin) (> zy-neu zemax))
                                   (line canvas sx zy sx-neu zy-neu))
                               (graph-zeichnen fkt (cons sx-neu zy-neu)))
                             (graph-zeichnen fkt (graph-startpkt fkt (cons (+ sx 1) zy))))))))))]
           [graph-list-zeichnen
            (lambda (fkt-ls anz color-ls)
              (if (not (null? fkt-ls))
                  (let ([fkt (eval (car fkt-ls))])
                    ((eval (n-tes-mod color-ls anz)) canvas)
                    (graph-zeichnen fkt (graph-startpkt fkt (cons spvon z0)))
                    (graph-list-zeichnen (cdr fkt-ls) (+ anz 1) color-ls))))])
        (koordcolor canvas)
        (if (< s0 spmin) (set! s0 spmin)) (if (> s0 spmax) (set! s0 spmax))
        (if (> z0 zemin) (set! z0 zemin)) (if (< z0 zemax) (set! z0 zemax))
        (line canvas spmin z0 spend z0)
        (line canvas s0 zemin s0 zeend)
        (line canvas (- spend 6) (- z0 2) spend z0)
        (line canvas (- spend 6) (+ z0 2) spend z0)
        (line canvas (- spend 6) (- z0 2) (- spend 6) (+ z0 2))
        (line canvas (- s0 2) (+ zeend 6) s0 zeend)
        (line canvas (+ s0 2) (+ zeend 6) s0 zeend)
        (line canvas (- s0 2) (+ zeend 6) (+ s0 2) (+ zeend 6))
        (set! mx (anpassen mx)) (set! teilerx (teilen mx))
        (set! stepx (/ (- spmax spmin) mx teilerx))
        (set! my (anpassen my)) (set! teilery (teilen my))
        (set! stepy (/ (- zemin zemax) my teilery))
        (x-teilen-positiv (+ s00 stepx)) (x-teilen-negativ (- s00 stepx))
        (y-teilen-positiv (- z00 stepy)) (y-teilen-negativ (+ z00 stepy))
        (set! ex (/ ex mx teilerx))
        (set! faktorx (faktor 
                       (* 3/2 textgroesse (string-length (number->string (genaurunden ex genau))))
                       stepx))
        (set! ey (/ ey my teilery))
        (set! faktory (faktor 
                       (* 3/2 textgroesse) 
                       stepy))
        (if (<= (abs yu) (abs yo))
            (begin
              (x-bezeichnen-positiv (+ s00 (* stepx faktorx)) (* ex faktorx) #t)
              (x-bezeichnen-negativ (- s00 (* stepx faktorx)) (- (* ex faktorx)) #t))
            (begin
              (x-bezeichnen-positiv (+ s00 (* stepx faktorx)) (* ex faktorx) #f)
              (x-bezeichnen-negativ (- s00 (* stepx faktorx)) (- (* ex faktorx)) #f)))
        (if (<= (abs xu) (abs xo))
            (begin
              (y-bezeichnen-positiv (- z00 (* stepy faktory)) (* ey faktory) #t)
              (y-bezeichnen-negativ (+ z00 (* stepy faktory)) (- (* ey faktory)) #t))
            (begin
              (y-bezeichnen-positiv (- z00 (* stepy faktory)) (* ey faktory) #f)
              (y-bezeichnen-negativ (+ z00 (* stepy faktory)) (- (* ey faktory)) #f)))
        (x-achse-bezeichnen bez)
        (y-achse-bezeichnen bez)
        (if (< spvon spmin) (set! spvon spmin)) (if (> spbis spmax) (set! spbis spmax))
        (graph-list-zeichnen fkt-list 0 color-list)
        'ok))))

(define anz 4)

(define runden
  (lambda (x anz)
    (/ (round (* x (expt 10 anz))) (expt 10 anz))))

(define nullstellenausgabe
  (lambda (fkt x)
    (let ([x0 (nst fkt x)])
      (display "Nullstelle: ")
      (if x0
          (display (number->string (runden x0 anz)))
          (display "--> keine"))
      (newline)
      'ok)))

(define termeingabe
  (lambda ()
    (let ([proz (read (open-input-string (inputDialog "Prozedur (Lambda-Term):")))])
      (with-failure-continuation
       (lambda (error-record error-k) #f)
       (lambda () (eval proz))))))

(define nullstelle
  (lambda (xu xo yu yo x-start)
    (let ([fkt (termeingabe)])
      (if fkt
          (begin
            (schaubild (list fkt) xu xo yu yo xu xo black '(red))
            (nullstellenausgabe fkt x-start))
          (begin
            (display "--> Eingabefehler!") (newline)
            'ok)))))

Die zu untersuchende mathematische Funktion geben wir dazu als Lambda-Term in einem Interaktionsfenster ein, z.B.:

(lambda (x) (- (sqr x) 2))

(nullstelle -10 10 -8 8 1)

Zurück zum Algorithmusbegriff.

Das Newton-Verfahren

Grundlagen

Implementation

Nullstellensuche und Schaubild

Suche