/prog/ - Complexity of Newtons Method

Name: Anonymous 2012-01-01 10:53

Can anone here explain to me how to find the computational complexity of Newtons Method for roots?

Name: Anonymous 2012-01-01 11:05

butts

Name: Anonymous 2012-01-01 11:58

pantyhose

Name: Anonymous 2012-01-01 18:42

Read SICP. (legit response)

Name: Anonymous 2012-01-01 18:42

>>1

yeah, first get a specific implementation of it together, and see if you can make any claims on how much closer it gets to the actual root after each iteration. You'll need to specify what function you are apply it to, and what value you'll be starting the iteration at, since newton's method doesn't always work in general.

Name: Anonymous 2012-01-01 19:20

doesn't always work
D= Noooo... my rockets!

Name: Anonymous 2012-01-02 0:21

(define (NM F D guess cnt)
(if (good-enough? F guess)
cnt
(NM F D (improve F D guess) (+ cnt 1) )))

(define (good-enough? F x)
(< (abs (F x)) 0.0001))

(define (improve F D guess)
(- (exact->inexact guess) (/ (F (exact->inexact guess)) (D (exact->inexact guess) ))))

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(define (T1 x)(+(* x x x)(* 4 x)16));;f(x)=x^3+4x+16
(define (T1d x) (+(* 3 x x)4));;f'(x)=3x^2+4

Name: Anonymous 2012-01-02 0:37

>>6

yeah, there are some functions where if you apply newton's method, it can overshoot the root. Sometimes it'll still find it, sometimes it'll overshoot it more and more, and end up bouncing back and forth between larger and larger negative and positive numbers. But if you set it up right with the right kind of function, you can prove that it'll converge, and you can get a sufficient amount of iterations required to obtain a desired small error. Think about the functions you are using geometrically, and find a good place to start it so that overshooting never happens. Then you can try to get some bounds on how fast it'll converge.

Name: Anonymous 2012-01-02 1:04

>>8 I have a little trick to combat this, you can average the last three 'computed' updates, and then use that average to perform the actual adjustment =) pretty simple eh

Name: Anonymous 2012-01-02 1:14

It's kind of equivalent to automatically adjusting the learning rate for each parameter seperately...

Eg. one feature goes 1,1,1 (/3 = 1)

Another might go 1, -1, 1 (/3 = 0.33)

Name: Anonymous 2012-01-02 1:27

>>9

that's neat. But you should test it on something like y = cube_root(x). I suspect that it would still be unstable, but that's cool that you are trying something new.

Name: Anonymous 2012-01-02 3:22

it is a bit unstable i think, (cost can spike upwards randomly, if that's what you mean?) =) if you asked me this 3 months ago I would've had no idea what newtons method is [^^ ml-class.org]

So, you're trying to figure out how to get to x^(1/3), given just a bunch of x,y pairs?

Name: Anonymous 2012-01-02 3:37

I think you could start with the simplest features first, and then slowly introduce more complex features... (gradient should tell you what is useful and what isn't..)

Eg. for y=2x + 2, start with the bias, and the gradient will go up above +2, then if you add in the x^1 term, bias will drop down to 2 and x^1 will also go to 2... (this is a perfect fit), so then if you try to add in x^2, the weight should stay at (or very near) 0, because adding weight to this term will make the hypothesis worse...

Good idea?

Name: Anonymous 2012-01-02 4:12

>>12

yeah, this is what happens if you run normal newton's method on y = cube_root(x). The goal is to get close to a value for x such that cube_root(x) is zero. You don't need to use newton's method to know that plugging in 0 for x will work though, so this isn't a very practical application. But it is a good example of how newton's method can fail sometimes.



y = cube_root(x)

                                 |

                                 |

                                 |                        ######

                                 |               #########

                                 |         ######

                                 |      ###

                                 |    ##

                                 |  ##

                                 | #

                                 |#

                                 #

---------------------------------#------------------------------

                                 #

                                #|

                               # |

                             ##  |

                           ##    |

                        ###      |

                  ######         |

          ########               |

##########                       |

                                 |

                                 |

                                 |



start point:





                                 |

                                 |

                                 |                        ######

                                 |               #########

                                 |         X#####

                                 |      ###

                                 |    ##

                                 |  ##

                                 | #

                                 |#

                                 #

---------------------------------#------------------------------

                                 #

                                #|

                               # |

                             ##  |

                           ##    |

                        ###      |

                  ######         |

          ########               |

##########                       |

                                 |

                                 |

                                 |





make tanget line:





                                 |                   XXX

                                 |                XXX

                                 |             XXX        ######

                                 |          XXX  #########

                                 |       XXX#####

                                 |    XX###

                                 | XXX##

                                XXX ##

                             XXX | #

                          XXX    |#

                       XXX       #

----------------------X----------#------------------------------

                                 #

                                #|

                               # |

                             ##  |

                           ##    |

                        ###      |

                  ######         |

          ########               |

##########                       |

                                 |

                                 |

                                 |



new point at intersection with x axis:



                                 |                   XXX

                                 |                XXX

                                 |             XXX        ######

                                 |          XXX  #########

                                 |       XXX#####

                                 |    XX###

                                 | XXX##

                                XXX ##

                             XXX | #

                          XXX    |#

                       XXX       #

----------------------X----------#------------------------------

                      :          #

                      :         #|

                      :        # |

                      :      ##  |

                      :    ##    |

                      : ###      |

                  ####O#         |

          ########               |

##########                       |

                                 |

                                 |

                                 |





next tangent line at new point:



                                 |                   XXX

                                 |                XXX

                                 |             XXX        ######

                                 |          XXX  #########

                                 |       XXX#####

                                 |    XX###

                                 | XXX##

                                XXX ##

                             XXX | #

                          XXX    |#

                       XXX       #

----------------------X----------#------------------------------O

                      :          #                        OOOOOO

                      :         #|                  OOOOOO

                      :        # |            OOOOOO

                      :      ##  |      OOOOOO

                      :    ##    |OOOOOO

                      : ### OOOOOO

                  ####OOOOOO     |

          ########               |

##########                       |

                                 |

                                 |

                                 |





start new point at intersection with x axis:



                                 |                      

                                 |                   

                                 |                        ######Z

                                 |               #########      :

                                 |       XXX#####               :

                                 |    XX###                     :

                                 | XXX##                        :

                                XXX ##                          :

                             XXX | #                            :

                          XXX    |#                             :

                       XXX       #                              :

----------------------X----------#------------------------------O

                      :          #                        OOOOOO

                      :         #|                  OOOOOO

                      :        # |            OOOOOO

                      :      ##  |      OOOOOO

                      :    ##    |OOOOOO

                      : ### OOOOOO

                  ####OOOOOO     |

          ########               |

##########                       |

                                 |

                                 |

                                 |







make new tangent line



                                 |                      

                                 |                   

                                 |             ZZZZZZZZZZZZZZZZZZ

                                ZZZZZZZZZZZZZZZ  #########      :

                 ZZZZZZZZZZZZZZZ |       XXX#####               :

  ZZZZZZZZZZZZZZZ                |    XX###                     :

ZZ                               | XXX##                        :

                                XXX ##                          :

(aw shucks)                  XXX | #                            :

                          XXX    |#                             :

                       XXX       #                              :

----------------------X----------#------------------------------O

                      :          #                        OOOOOO

                      :         #|                  OOOOOO

                      :        # |            OOOOOO

                      :      ##  |      OOOOOO

                      :    ##    |OOOOOO

                      : ### OOOOOO

                  ####OOOOOO     |

          ########               |

##########                       |

                                 |

                                 |

                                 |

I'm not sure what would happen with your modifications. It might work.

Name: Anonymous 2012-01-02 4:19

>>13

yeah I'm not sure. But if you want to handle situations where newton's method fails you could try checking out other methods for finding roots. One of the simplest methods is to find two points on the function with one point being above zero, and the other below zero, and you then do binary search looking for the point at which the function crosses the x axis. This will always find a root for a continuous function in time proportional to the log of the length of the interval being searched, which is linear in the length of the base two representation of the answer.

Name: Anonymous 2012-01-02 4:21

>>13
and it is best to keep things as simple as possible. If you start making designing something that you think might work, it most likely isn't going to work, at least not for every case, especially in an application like this. You want to get something simple and dependable with performance that you can predict well. Otherwise it might not work, or it might take forever to converge to something useful.

Name: sage 2012-01-02 4:40

>having problems with Newton's Method
SICP is RIGHT THERE, IT HAS ALWAYS BEEN RIGHT THERE, SECOND EPISODE OR SOMETHING, GOOD LORD

Like you faggots that can't understand pointers or pixels v voxels, I don't know how your brains remember to breath

Name: Anonymous 2012-01-02 6:11

>>17

http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-4.html

1.1.7



Exercise 1.6.  Alyssa P. Hacker doesn't see why if needs to be provided as a special form. ``Why can't I just define it as an ordinary procedure in terms of cond?'' she asks. Alyssa's friend Eva Lu Ator claims this can indeed be done, and she defines a new version of if:



(define (new-if predicate then-clause else-clause)

  (cond (predicate then-clause)

        (else else-clause)))

What was wrong with the old IF ??

Name: Anonymous 2012-01-02 6:23



Eva demonstrates the program for Alyssa:



(new-if (= 2 3) 0 5)

5



(new-if (= 1 1) 0 5)

0



Delighted, Alyssa uses new-if to rewrite the square-root program:



(define (sqrt-iter guess x)

  (new-if (good-enough? guess x)

          guess

          (sqrt-iter (improve guess x)

                     x)))



What happens when Alyssa attempts to use this to compute square roots? Explain.

you f###ing EXPLAIN, it's your book

Name: Anonymous 2012-01-02 6:34

>>17
You don't have to remember how to breathe, it's part of the autonomic system which operates (if possible) even in a vegetative state.

Name: Anonymous 2012-01-02 6:41

>>19
you could always try it yourself.

Name: Anonymous 2012-01-02 6:53

>>21 perhaps.. i could explain...

Obviously, Lisp is such a piece of junk that it doesn't even ship with a properly functioning "if" statement... Allysa is delighted because she is retarded..

SICP itself is recommended to everyone because it is so rage-worthy, and knuckle-heads enjoy pissing other people off...

...Should i continue? I think i've explained just about everything..

Name: Anonymous 2012-01-02 7:08

>>22
Writing with ellipsis everywhere
You're the retard.

Name: Anonymous 2012-01-02 7:10

>>19

new-if is a function, so all of its arguments are evaluated, no matter what. So code in both branches is always executed, although the result of only one branch is returned. But in this case, always evaluating both branches likely leads to infinite recursion.

Name: Anonymous 2012-01-02 7:38

ONE WORD THE FORCED EAGER EVALUATION OF FUNCTION PARAMETERS THREAD OVER.

Name: Anonymous 2012-01-02 7:45

...yeah ()()()))(())) ;)
to be fair though, this bit was good:



For example, we can compute the square root of 2 as follows. Suppose our initial guess is 1:



Guess     Quotient     Average

  

1     (2/1) = 2     ((2 + 1)/2) = 1.5

  

1.5     (2/1.5) = 1.3333     ((1.3333 + 1.5)/2) = 1.4167

  

1.4167     (2/1.4167) = 1.4118     ((1.4167 + 1.4118)/2) = 1.4142

  

1.4142     ...    ...



Continuing this process, we obtain better and better approximations to the square root.

I would've liked more explanation on how/why this works for square roots, and how it was found though... rather than.. blah i'll shut up and google newtons method on wikipedia

Name: Anonymous 2012-01-02 8:15

found this: http://en.wikipedia.org/wiki/Householder%27s_method

yeah i was thinking of gradient descent (They are pretty similar though... sort of... not really.. =P i dunno..)

How do you do x^(1/2.5) // two point fifth root? (No such thing..?)

oh shit its hell simple... 2 / 1.5 [ = 1.5 ?] (as in 1.5 * 1.5 = 2 ? )

so a cuberoot would be 2 / (1.5 * 1.5) [ = 1.5 ?]...? and 2.5 is a pain? =)

Name: Anonymous 2012-01-02 8:35

>>26

yeah, the formula you are using for finding the square root of a is:

x_{n+1} = (1/2)(x_n + a/x_n)

Note that by finding the square root of a, you are finding the positive root of the function, y = x^2 - a.

When doing newtons method you create a tangent line at x_n,

T(x) = m(x - x_0) + y_0 = f'(x_n)(x - x_n) + f(x_n)
and find the intersection T has with the x-axis

T(x) = 0
f'(x_n)(x - x_n) + f(x_n) = 0
f'(x_n)(x_n - x) = f(x_n)
(x_n - x) = (f(x_n))/(f'(x_n))
x = x_n - (f(x_n))/(f'(x_n))

and then you use this intersection with the x-axis as your new point:

x_{n+1} = x_n - (f(x_n))/(f'(x_n))

Now suppose that f(x) = x^2 - a.

then

f'(x) = 2x

so

x_{n+1} = x_n - (f(x_n))/(f'(x_n))
      = x_n - ((x_n)^2 - a)/(2(x_n))
      = x_n - ((x_n)^2 - a)/(2(x_n))
      = x_n - ((1/2)(x_n) - (1/2)(a/x_n))
      = x_n - (1/2)(x_n) + (1/2)(a/x_n)
      = (1/2)(x_n) + (1/2)(a/x_n)
      = (1/2)(x_n + a/x_n)

So yeah, it is just a newton's method applied to f(x) = x^2 - a.

Anyways can you get a bounds on how fast it'll converge? Like, if x_n is d away from the square root of a, then can you get a bound on how far away x_{n+1} is to the square root of a? Doo eeet!

Name: Anonymous 2012-01-02 8:47

>>27

if you are lazy and have an e^x and a ln(x) function, and you need to find a^x, then you can do:

a^x = e^ln(a^x) = e^(log_a(a^x)/ln(a)) = e^(x/ln(a))

so dat is alwaz nice. <|:)

But if you want to do it yourself, and take x^(p/q), you can first find x^(1/q), and then take the result to the p power. Or you could just take the qth root of x^p. So it reduces pretty easily to finding the nth root of a, for some n. And that is just

x = a^(1/n)
x^n = a
0 = x^n - a

So you can try to find da roots of f(x) = x^n - a, using newton's method if you wishd.

Name: Anonymous 2012-01-02 16:00

Whats with all this math shit? I just wanna hack or make video games and shit.

Name: Anonymous 2012-01-02 16:19

>>30
Whats with all this math shit? I just wanna ~~hack~~ or ~~make video games~~ and shit.

Everyone can do shit, pal.

Complexity of Newtons Method

1 Name: Anonymous 2012-01-01 10:53

2 Name: Anonymous 2012-01-01 11:05

3 Name: Anonymous 2012-01-01 11:58

4 Name: Anonymous 2012-01-01 18:42

5 Name: Anonymous 2012-01-01 18:42

6 Name: Anonymous 2012-01-01 19:20

7 Name: Anonymous 2012-01-02 0:21

8 Name: Anonymous 2012-01-02 0:37

9 Name: Anonymous 2012-01-02 1:04

10 Name: Anonymous 2012-01-02 1:14

11 Name: Anonymous 2012-01-02 1:27

12 Name: Anonymous 2012-01-02 3:22

13 Name: Anonymous 2012-01-02 3:37

14 Name: Anonymous 2012-01-02 4:12

15 Name: Anonymous 2012-01-02 4:19

16 Name: Anonymous 2012-01-02 4:21

17 Name: sage 2012-01-02 4:40

18 Name: Anonymous 2012-01-02 6:11

19 Name: Anonymous 2012-01-02 6:23

20 Name: Anonymous 2012-01-02 6:34

21 Name: Anonymous 2012-01-02 6:41

22 Name: Anonymous 2012-01-02 6:53

23 Name: Anonymous 2012-01-02 7:08

24 Name: Anonymous 2012-01-02 7:10

25 Name: Anonymous 2012-01-02 7:38

26 Name: Anonymous 2012-01-02 7:45

27 Name: Anonymous 2012-01-02 8:15

28 Name: Anonymous 2012-01-02 8:35

29 Name: Anonymous 2012-01-02 8:47

30 Name: Anonymous 2012-01-02 16:00

31 Name: Anonymous 2012-01-02 16:19

Name: Anonymous 2012-01-01 10:53

Name: Anonymous 2012-01-01 11:05

Name: Anonymous 2012-01-01 11:58

Name: Anonymous 2012-01-01 18:42

Name: Anonymous 2012-01-01 18:42

Name: Anonymous 2012-01-01 19:20

Name: Anonymous 2012-01-02 0:21

Name: Anonymous 2012-01-02 0:37

Name: Anonymous 2012-01-02 1:04

Name: Anonymous 2012-01-02 1:14

Name: Anonymous 2012-01-02 1:27

Name: Anonymous 2012-01-02 3:22

Name: Anonymous 2012-01-02 3:37

Name: Anonymous 2012-01-02 4:12

Name: Anonymous 2012-01-02 4:19

Name: Anonymous 2012-01-02 4:21

Name: sage 2012-01-02 4:40

Name: Anonymous 2012-01-02 6:11

Name: Anonymous 2012-01-02 6:23

Name: Anonymous 2012-01-02 6:34

Name: Anonymous 2012-01-02 6:41

Name: Anonymous 2012-01-02 6:53

Name: Anonymous 2012-01-02 7:08

Name: Anonymous 2012-01-02 7:10

Name: Anonymous 2012-01-02 7:38

Name: Anonymous 2012-01-02 7:45

Name: Anonymous 2012-01-02 8:15

Name: Anonymous 2012-01-02 8:35

Name: Anonymous 2012-01-02 8:47

Name: Anonymous 2012-01-02 16:00

Name: Anonymous 2012-01-02 16:19