反復法

home > さまざまな言語で数値計算 > 非線形方程式 >

反復法

非線形方程式の解法（反復法または単純代入法とも言う）を利用して2の平方根を求める .

1. まず, 方程式 $ f(x) = 0 $ を, $ x = g(x) $ と変形する.

2. $ g(x) $ の値を新しい $x$ として処理を繰り返して行くことで解を求める.

ただし, 曲線 $ y = g(x) $ の傾きが, $ y = x $ の傾きより小さくなければ収束しない.

例

を

と変形しても収束しない.

そこで一工夫して

と変形してみると

傾きが, $ y = x $ の傾きより小さくなって収束する.

VBScript

Option Explicit

Dim x: x = 1.0
WScript.StdOut.Write Right(Space(12) & FormatNumber(iterative(x), 10, -1, 0, 0), 12) & vbNewLine

Private Function iterative(ByVal x0)
    Dim x1
    Do While(True)
        x1 = g(x0)
        WScript.StdOut.Write Right(Space(12) & FormatNumber(x1,          10, -1, 0, 0), 12) & vbTab
        WScript.StdOut.Write Right(Space(12) & FormatNumber(x1 - Sqr(2), 10, -1, 0, 0), 12) & vbNewLine

        If Abs(x1 - x0) < 0.0000000001 Then Exit Do
        x0 = x1
    Loop

    iterative = x1
End Function

Private Function g(ByVal x)
    g = (x / 2) + (1 / x)
End Function

Z:\>cscript //nologo Z:\0903.vbs
1.5000000000    0.0857864376
1.4166666667    0.0024531043
1.4142156863    0.0000021239
1.4142135624    0.0000000000
1.4142135624    0.0000000000
1.4142135624

JScript

var x = 1
WScript.StdOut.Write(("            " + iterative(x).toFixed(10) ).slice(-12) + "\n")

function iterative(x0) {
    var x1
    while (true) {
        x1 = g(x0)
        WScript.StdOut.Write(("            " + x1.toFixed(10)                  ).slice(-12) + "\t")
        WScript.StdOut.Write(("            " + (x1 - Math.sqrt(2)).toFixed(10) ).slice(-12) + "\n")

        if (Math.abs(x1 - x0) < 0.0000000001) break
        x0 = x1
    }
    return x1
}

function g(x) {
    return (x / 2) + (1 / x)
}

Z:\>cscript //nologo Z:\0903.js
1.5000000000    0.0857864376
1.4166666667    0.0024531043
1.4142156863    0.0000021239
1.4142135624    0.0000000000
1.4142135624    0.0000000000
1.4142135624

PowerShell

function iterative($x0)
{
    while ($true)
    {
        $x1 = g($x0)
        Write-Host ([String]::Format("{0,12:F10}`t{1,13:F10}", $x1, $x1 - [Math]::Sqrt(2)))

        if ([Math]::Abs($x1 - $x0) -lt 0.0000000001)
        {
            break
        }
        $x0 = $x1
    }
    return $x1
}

function g($x)
{
    return ($x / 2) + (1 / $x)
}

$x = 1
Write-Host ([String]::Format("{0,12:F10}", (iterative $x)))

Z:\>powershell -file Z:\0903.ps1
1.5000000000     0.0857864376
1.4166666667     0.0024531043
1.4142156863     0.0000021239
1.4142135624     0.0000000000
1.4142135624     0.0000000000
1.4142135624

Perl

my $x = 1;
printf("%12.10f\n", iterative($x));

sub iterative
{
    my ($x0) = @_;
    my $x1;
    while (1)
    {
        $x1 = g($x0);
        printf("%12.10f\t%13.10f\n", $x1, $x1 - sqrt(2));

        if (abs($x1 - $x0) < 0.0000000001)
        {
            last;
        }
        $x0 = $x1;
    }
    $x1;
}

sub g
{
    my ($x) = @_;
    ($x / 2) + (1 / $x);
}

Z:\>perl Z:\0903.pl
1.5000000000     0.0857864376
1.4166666667     0.0024531043
1.4142156863     0.0000021239
1.4142135624     0.0000000000
1.4142135624    -0.0000000000
1.4142135624

PHP

<?php
$x = 1;
printf("%12.10f\n", iterative($x));

function iterative($x0)
{
    while (TRUE)
    {
        $x1 = g($x0);
        printf("%12.10f\t%13.10f\n", $x1, $x1 - sqrt(2));

        if (abs($x1 - $x0) < 0.0000000001) break;

        $x0 = $x1;
    }
    return $x1;
}

function g($x)
{
    return ($x / 2) + (1 / $x);
}
?>

Z:\>php Z:\0903.php
1.5000000000     0.0857864376
1.4166666667     0.0024531043
1.4142156863     0.0000021239
1.4142135624     0.0000000000
1.4142135624    -0.0000000000
1.4142135624

Python

# coding: Shift_JIS

import math

def g(x):
    return (x / 2.0) + (1.0 / x)

def iterative(x0):
    while True:
        x1 = g(x0)
        print "%12.10f\t%13.10f" % (x1, x1 - math.sqrt(2))

        if (abs(x1 - x0) < 0.0000000001):
            break
        x0 = x1

    return x1

x = 1.0
print "%12.10f" % iterative(x)

Z:\>python Z:\0903.py
1.5000000000     0.0857864376
1.4166666667     0.0024531043
1.4142156863     0.0000021239
1.4142135624     0.0000000000
1.4142135624    -0.0000000000
1.4142135624

Ruby

include Math

def g(x)
    (x / 2.0) + (1.0 / x)
end

def iterative(x0)
    while true
        x1 = g(x0)
        printf("%12.10f\t%13.10f\n", x1, x1 - sqrt(2))

        if (x1 - x0).abs < 0.0000000001
            break
        end

        x0 = x1
    end

    x1
end

x = 1.0
printf("%12.10f\n", iterative(x))

Z:\>ruby Z:\0903.rb
1.5000000000     0.0857864376
1.4166666667     0.0024531043
1.4142156863     0.0000021239
1.4142135624     0.0000000000
1.4142135624    -0.0000000000
1.4142135624

Groovy

x = 1
printf ("%12.10f\n" , iterative(x))

def iterative(x0) {
    while (true) {
        x1 = g(x0)
        printf("%12.10f\t%13.10f\n", x1, x1 - Math.sqrt(2))

        if (Math.abs(x1 - x0) < 0.0000000001) break
        x0 = x1
    }
    x1
}

def g(x) {
    (x / 2) + (1 / x)
}

Z:\>groovy Groovy0903.groovy
1.5000000000     0.0857864376
1.4166666667     0.0024531043
1.4142156863     0.0000021239
1.4142135624     0.0000000000
1.4142135624     0.0000000000
1.4142135624

Pascal

program Pas0903(arg);
{$MODE delphi}

uses
    SysUtils, Math;

function g(x:Double):Double;
begin
    result := (x / 2) + (1 / x);
end;

function iterative(x0:Double):Double;
var
    x1: Double;
begin
    while true do
    begin
        x1 := g(x0);
        writeln(format('%12.10f'#9'%13.10f', [x1, x1 - Sqrt(2)]));

        if Abs(x1 - x0) < 0.0000000001 then break;
        x0 := x1;
    end;

    result := x1;
end;

var
    x:  Double = 1.0;
begin
    writeln(format('%12.10f', [iterative(x)]));
end.

Z:\>fpc -v0 -l- Pas0903.pp

Z:\>Pas0903
1.5000000000     0.0857864376
1.4166666667     0.0024531043
1.4142156863     0.0000021239
1.4142135624     0.0000000000
1.4142135624     0.0000000000
1.4142135624

Ada

with TEXT_IO, Ada.Long_Float_Text_IO, Ada.Numerics.Long_Elementary_Functions;
use  TEXT_IO, Ada.Long_Float_Text_IO, Ada.Numerics.Long_Elementary_Functions;

procedure Ada0903 is

    function g(x:Long_Float) return Long_Float is
    begin
        return (x / 2.0) + (1.0 / x);
    end g;

    function iterative(x:Long_Float) return Long_Float is
        x0: Long_Float;
        x1: Long_Float;
    begin
        x0 := x;
        while true loop
            x1 := g(x0);
            Put(x1,             Fore=>2, Aft=>10, Exp=>0);
            Put(Ascii.HT);
            Put(x1 - Sqrt(2.0), Fore=>2, Aft=>10, Exp=>0);
            New_Line;

            if Abs(x1 - x0) < 0.0000000001 then
                exit;
            end if;
            x0 := x1;
        end loop;

        return x1;
    end iterative;

    x: Long_Float := 1.0;
begin
    Put(iterative(x), Fore=>2, Aft=>10, Exp=>0);
    New_Line;
end Ada0903;

xxxxxx@yyyyyy /Z
$ gnatmake Ada0903.adb

xxxxxx@yyyyyy /Z
$ Ada0903
 1.5000000000    0.0857864376
 1.4166666667    0.0024531043
 1.4142156863    0.0000021239
 1.4142135624    0.0000000000
 1.4142135624    0.0000000000
 1.4142135624

VB.NET

Option Explicit

Module VB0903
    Public Sub Main()
        Dim x As Double = 1.0
        Console.WriteLine(String.Format("{0,12:F10}", iterative(x)))
    End Sub

    Private Function iterative(ByVal x0 As Double)
        Dim x1 As Double
        Do While(True)
            x1 = g(x0)
            Console.WriteLine(String.Format("{0,12:F10}{2}{1,13:F10}", x1, x1 - Math.Sqrt(2), vbTab))

            If Math.Abs(x1 - x0) < 0.0000000001 Then Exit Do
            x0 = x1
        Loop

        Return x1
    End Function

    Private Function g(ByVal x As Double) As Double
        Return (x / 2) + (1 / x)
    End Function
End Module

Z:\>vbc -nologo VB0903.vb

Z:\>VB0903
1.5000000000     0.0857864376
1.4166666667     0.0024531043
1.4142156863     0.0000021239
1.4142135624     0.0000000000
1.4142135624     0.0000000000
1.4142135624

C#

using System;

public class CS0903
{
    public static void Main()
    {
        double x = 1;
        Console.WriteLine(string.Format("{0,12:F10}", iterative(x)));
    }

    private static double iterative(double x0)
    {
        double x1;
        while (true)
        {
            x1 = g(x0);
            Console.WriteLine(string.Format("{0,12:F10}\t{1,13:F10}", x1, x1 - Math.Sqrt(2)));

            if (Math.Abs(x1 - x0) < 0.0000000001) break;
            x0 = x1;
        }
        return x1;
    }

    private static double g(double x)
    {
        return (x / 2) + (1 / x);
    }
}

Z:\>csc -nologo CS0903.cs

Z:\>CS0903
1.5000000000     0.0857864376
1.4166666667     0.0024531043
1.4142156863     0.0000021239
1.4142135624     0.0000000000
1.4142135624     0.0000000000
1.4142135624

Java

import static java.lang.System.out;

public class Java0903 {

    public static void main(String []args) {
        double x = 1;
        out.println(String.format("%12.10f", iterative(x)));
    }

    private static double iterative(double x0) {
        double x1;
        while (true) {
            x1 = g(x0);
            out.println(String.format("%12.10f\t%13.10f", x1, x1 - Math.sqrt(2)));

            if (Math.abs(x1 - x0) < 0.0000000001) break;
            x0 = x1;
        }
        return x1;
    }

    private static double g(double x) {
        return (x / 2) + (1 / x);
    }
}

Z:\>javac Java0903.java

Z:\>java Java0903
1.5000000000     0.0857864376
1.4166666667     0.0024531043
1.4142156863     0.0000021239
1.4142135624     0.0000000000
1.4142135624    -0.0000000000
1.4142135624

C++

#include <iostream>
#include <iomanip>
#include <math.h>

using namespace std;

double g(double x)
{
    return (x / 2) + (1 / x);
}

double iterative(double x0)
{
    double x1;
    while (true)
    {
        x1 = g(x0);
        cout << setw(12) << fixed << setprecision(10) << x1 << "\t";
        cout << setw(13) << fixed << setprecision(10) << x1 - sqrt(2) << endl;

        if (fabs(x1 - x0) < 0.0000000001) break;
        x0 = x1;
    }
    return x1;
}

int main()
{
    double x = 1.0;
    cout << setw(12) << fixed << setprecision(10) << iterative(x) << endl;
    return 0;
}

Z:\>bcc32 -q CP0903.cpp
cp0903.cpp:

Z:\>CP0903
1.5000000000     0.0857864376
1.4166666667     0.0024531043
1.4142156863     0.0000021239
1.4142135624     0.0000000000
1.4142135624     0.0000000000
1.4142135624

Objective-C

#import <Foundation/Foundation.h>
#import <math.h>

double g(double x)
{
    return (x / 2) + (1 / x);
}

double iterative(double x0)
{
    double x1;
    while (YES)
    {
        x1 = g(x0);
        printf("%12.10f\t%13.10f\n", x1, x1 - sqrt(2));

        if (fabs(x1 - x0) < 0.0000000001) break;
        x0 = x1;
    }
    return x1;
}

int main()
{
    double x = 1;
    printf("%12.10f\n", iterative(x));
    return 0;
}

xxxxxx@yyyyyy /Z
$ gcc -o OC0903 OC0903.m -lobjc -lgnustep-base -I $INCLUDE -L $LIB $CFLAGS

xxxxxx@yyyyyy /Z
$ OC0903
1.5000000000     0.0857864376
1.4166666667     0.0024531043
1.4142156863     0.0000021239
1.4142135624     0.0000000000
1.4142135624     0.0000000000
1.4142135624

D

import std.stdio;
import std.math;

void main(string[] args)
{
    double x = 1;
    writefln("%12.10f", iterative(x));
}

double iterative(double x0)
{
    double x1;
    while (true)
    {
        x1 = g(x0);
        writefln("%12.10f\t%13.10f", x1, x1 - sqrt(2.0));

        if (fabs(x1 - x0) < 0.0000000001) break;
        x0 = x1;
    }
    return x1;
}

double g(double x)
{
    return (x / 2) + (1 / x);
}

Z:\>dmd D0903.d

Z:\>D0903
1.5000000000     0.0857864376
1.4166666667     0.0024531042
1.4142156863     0.0000021239
1.4142135624     0.0000000000
1.4142135624     0.0000000000
1.4142135624

Go

package main

import "fmt"
import "math"

func main() {
    var x float64 = 1
    fmt.Printf("%12.10f\n", iterative(x))
}

func iterative(x0 float64) float64 {
    var x1 float64
    for {
        x1 = g(x0)
        fmt.Printf("%12.10f\t%13.10f\n", x1, x1 - math.Sqrt(2))

        if math.Fabs(x1 - x0) < 0.0000000001 {
            break
        }
        x0 = x1
    }
    return x1
}

func g(x float64) float64 {
    return (x / 2) + (1 / x)
}

Z:\>8g GO0903.go

Z:\>8l -o GO0903.exe GO0903.8

Z:\>GO0903
1.5000000000     0.0857864376
1.4166666667     0.0024531043
1.4142156863     0.0000021239
1.4142135624     0.0000000000
1.4142135624    -0.0000000000
1.4142135624

Scala

object Scala0903 {

    def main(args: Array[String]) {
        val x = 1.0
        println("%12.10f".format(iterative(x)))
    }

    def iterative(x0:Double):Double = {
        val x1 = g(x0)
        println("%12.10f\t%13.10f".format(x1, x1 - Math.sqrt(2)))

        if (Math.abs(x1 - x0) < 0.0000000001)
            x1
        else
            iterative(x1)
    }

    def g(x:Double) = {
        (x / 2) + (1 / x)
    }
}

Z:\>scala Scala0903.scala
1.5000000000     0.0857864376
1.4166666667     0.0024531043
1.4142156863     0.0000021239
1.4142135624     0.0000000000
1.4142135624    -0.0000000000
1.4142135624

F#

module Fs0903

open System

let g (x:double):double =
    (x / 2.0) + (1.0 / x)

let rec iterative (x0:double):double =
    let x1 = g(x0)
    printfn "%12.10f\t%13.10f" x1 (x1 - Math.Sqrt(2.0))

    if abs(x1 - x0) < 0.0000000001 then
        x1
    else
        iterative x1

let x = 1.0
printfn "%12.10f" (iterative x)

exit 0

Z:\>fsi  --nologo --quiet Fs0903.fs
1.5000000000     0.0857864376
1.4166666667     0.0024531043
1.4142156863     0.0000021239
1.4142135624     0.0000000000
1.4142135624     0.0000000000
1.4142135624

Clojure

(defn g[x]
    (+ (/ x 2.0) (/ 1.0 x)))

(defn iterative [x0]
    (def x1 (g x0))
    (println (format "%12.10f\t%13.10f" x1 (- x1 (Math/sqrt 2))))

    (if (< (. Math abs (- x1 x0)) 0.00000000001)
        x1
        (iterative x1)))

(def x 1.0)
(println (format "%12.10f" (iterative x)))

Z:\>java -cp C:\ProgramFiles\clojure-1.5.1\clojure-1.5.1.jar clojure.main Clj0903.clj
1.5000000000     0.0857864376
1.4166666667     0.0024531043
1.4142156863     0.0000021239
1.4142135624     0.0000000000
1.4142135624    -0.0000000000
1.4142135624

Haskell

import Text.Printf
import Debug.Trace

g::Double->Double
g x = (x / 2.0) + (1.0 / x)

iterative::Double->Double
iterative x0 =
    let
        x1 = (g x0)
    in
        if abs(x1 - x0) < 0.0000000001 then
            x1
        else
            trace (printf "%12.10f\t%13.10f" x1 (x1 - ((sqrt 2.0)::Double)))
            iterative x1

main = do
    let x = 1.0
    printf "%12.10f\n" (iterative x)

Z:\>runghc Hs0903.hs
1.5000000000     0.0857864376
1.4166666667     0.0024531043
1.4142156863     0.0000021239
1.4142135624     0.0000000000
1.4142135624

VBScript
JScript
PowerShell
Perl
PHP
Python
Ruby
Groovy

Pascal
Ada
VB.NET

C#
Java
C++
Objective-C
D
Go

Scala
F#
Clojure
Haskell