math 201

[mikegoo]

Since some smarter folks than myself might look at this here.

Regarding Newton-Raphson Method (or just Newton's Method) for approximating zeros of a function:

Xn+1 = Xn - f(Xn)/ f'(Xn) (too incompetent to get subscripts)

Does anyone have any insights into the convergence or divergence of the resulting series. I've been doing a bit of reading and have found very little...other than a couple of things that involve knowing the value of the zero (seems rather silly to me) or a test for convergence where failure does not mean divergence. Any help would be appreciated.

[mith]

Regarding the injection thing (we call it 1-1), yeah, if I remember correctly, you can only prove that with the AoC or an equivalent (we used Well Ordering, I think). If you have that, you can basically just do what CB said.

[Bicho the Inhaler]

mikegoo -

From Rudin, Principles of Mathematical Analysis, 3rd ed. (p. 118):

"Suppose f is twice differentiable on [a, b], f(a) < 0, f(b) > 0, f'(x) >= d > 0 (for some positive constant d), and 0 <= f''(x) <= M (for some positive constant M) for all x in [a, b]. Let x be the unique point in (a, b) at which f(x) = 0.
...
Choose x_1 in (x, b) and define {x_n} by
...
x_(n+1) = x_n - f(x_n)/f'(x_n).
...
x_(n+1) < x_n and lim(as n -> infinity)x_n = x."

In other words, the sequence is guaranteed to converge to the zero of f if your initial guess x_1 falls in an interval [a, b] containing x on which f satisfies those properties. By symmetry, of course, it doesn't matter if your initial guess is greater than or less than the actual root. It doesn't involve knowing exactly where the zero is, but your initial guess has to conform to a certain standard. I've never heard of a test for divergence; maybe someone else has.

[extropalopakettle]

quote:

---

Regarding Newton-Raphson Method (or just Newton's Method) for approximating zeros of a function:

Xn+1 = Xn - f(Xn)/ f'(Xn) (too incompetent to get subscripts)

Does anyone have any insights into the convergence or divergence of the resulting series.

---

Not sure what you're looking for, but I do know this much: it's chaotic. Years ago I wrote some programs to plot which of multiple zeroes different starting points (X₀) led to (using complex numbers). If there are three zeroes, let's say, you color the complex plain three colors, each point colored to indicate which of the three zeroes the Newton-Raphson method ends up at with that as a starting point. The borders between the colored regions are "infinitely complex" - you can magnify them and get more and more detail. A quich Yahoo search on "Newton-Raphson fractals" will get you lot's of pictures on what I'm talking about (as well as better explanations, I'm sure).

[extropalopakettle]

Here's a really cool animation, from this page, graphing the results of Newton-Raphson for a 3-zeroed polynomial, as the zeroes move along a continuous curve (i.e. each frame of the animation is for a slightly different polynomial).

[CrystyB]

i might be a bit thick, but where does the second dimension come from??

[extropalopakettle]

Complex numbers - the real an imaginary component. You have an orthogonal real and imaginary axis, and each point on the plane maps to a unique complex number. For each point, use it as the starting value in Newton-Raphson (with a polynomial with known zeroes), and iterate until you reach one of the zeroes. Color the original point according to which zero you end up at (maybe also shade it according to how many iterations it took).

Then for the animations, each frame is for a different polynomial, where the polynomials are generated by first picking some points at which they'll evaluate to zero, and moving these along some continuous path for the different polynomials for the different frames.

[CrystyB]

so the polynom used in this particular case is thought to be C->C?... Bah, i guess i never really had to decompose polynoms which have complex roots!

[extropalopakettle]

Still, I think for a polynomials in the strictly real domain, you'll still get fractals, though 1-dimensional. Say the polynomial has three zeroes. Color the real line three colors according to which zero each point on the line leads to with Newton-Raphson. I think the boundaries between different colored regions of the line won't be sharp, but will have infinitely many infinitely small alternating segments of different colors. I think.

[mikegoo]

Thanks...I completely forgot that there is no such thing as a divergence test for N-R.... I knew there was a reason I didn't like this the last time I looked at it... yet even this makes no sense since I looked into the fractals resulting from this... my brain just isn't what it used to be.

[borschevsky]

quote:

---

Define the sequence a(n) as
a(1) = 1
a(n + 1) = 4*a(n) + 1

for finite positive integers n. (No problems here because surreal addition and multiplication are easy.) Let L be the set { a(n)*4^-n such that n is a finite positive integer } and let R be the set { (a(n) + 1)*4^-n such that n is a finite positive integer }. {L | R} is a valid surreal number and has all of the properties we associate with 1/3.

---

Yeah, that does look like an easier way to do it. Any sequences that go to 1/3 from below and above should work, though, right? We could use my L & R and throw out all the elements that aren't "close" to 1/3, or we could use your sequences and throw out the first 1000 elements, or all the even-numbered elements, etc.

How are other numbers (sqrt(2), pi, e) defined? I think the definition I was using should work for any number; just use that number instead of 1/3 in the definition.

[mith]

For pi you could use:

L={(4-4/3) , (4-4/3+4/5-4/7) , (4-4/3+4/5-4/7+4/9-4/11) , ...}
R={4 , (4-4/3+4/5) , (4-4/3+4/5-4/7+4/9) , ...}

[CrystyB]

_{Solve     x} ( y^z ) _{= ( x^y )}^z_{,     where x,y,zÎN*, i.e. integers ³1.}

[This message has been edited by CrystyB (edited 05-31-2003 09:31 PM).]

[Lucky Wizard]

By one of the laws of exponents, (x^y)^z = x^yz. Hence, x^yz = _x(y^z). Taking the logarithm in base x of both sides gives yz=y^z. I can't prove it, but the only natural numbers for which this could be true are z=1 (in which case y could be any natural number) and z=2 (in which case y could only be 2). So these are both solutions:

x=anything; y=anything; z=1
x=anything; y=2; z=2

[CrystyB]

grade: C (let's not forget this is 201...)

You can take the log only if the base is <> 1. That's why you missed a whole class of solutions: 1/anything/anything.
And proving z=y^z-1 for z>1 => y=z=2 is easy, either by induction or by noticing one is linear and the other exponential...

[This message has been edited by CrystyB (edited 06-01-2003 11:23 PM).]

[Bicho the Inhaler]

x^(y^z) = (x^y)^z is equivalent to
x^(y^z) = x^(yz)

Because everything is positive, take the natural log of both sides without losing any information:

(y^z)log x = (yz)log x

This would be true if log x = 0, i.e., if x = 1. This is one class of solutions ({(1, y, z) for any legal y, z}). If log x <> 0, divide by it to get:
y^z = yz
y^(z - 1) = z.
Note that this will be satisfied if z = 1. This is another class of solutions. Now suppose z > 1, so z - 1 > 0. In this case we can take the (z - 1)-th root of both sides, so now we have

y = z^(1/(z - 1)).

Let the function f be defined with domain N* and co-domain reals by f(z) := z^(1/(z - 1)). First, note that f(2) = 2, which is another solution to the equation. Shortly, we'll prove that there are no more solutions.

Second, suppose f(z) = 1. Then we take the natural logarithm to get:
0 = log(z)/(z - 1) (remembering that z - 1 > 0). But now we must have log(z) = 0, implying z = 1, which is definitely not true. Therefore f never attains 1 on our domain.

Third, we prove that f is strictly decreasing on our domain. All we really need to show is that f(a) > f(a + 1) for all integers a >= 2.

f(a) = a^(1/(a - 1))
f(a + 1) = (a + 1)^(1/a)

Note that (f(a)/(f(a + 1))^((a)(a - 1)) > 1 iff f(a)/f(a + 1) > 1 iff f(a) > f(a + 1).

(f(a)/f(a + 1))^((a)(a - 1)) = a^a/(a + 1)^(a - 1)
= (a + 1)a^a/(a + 1)^a.

Let's look at (a + 1)^a. By the binomial theorem we expand this to
a^a + (a)*a^(a - 1) + (1/2)(a)(a - 1)*a^(a - 2) + ... + (1/a!)(a!)*a^(a - a)

< a^a + (a)*a^(a - 1) + (1/2)(a)(a)*a^(a - 2) + ... + (1/a!)(a)^a (here, all we did was note that if for each term of the sum, we replace all the factors of form (a - i) that we get by applying the binomial theorem with (a), the result will be greater than the original.)

= a^a + a^a + 1/2*a^a + ... + 1/a!*a^a (combined powers of a in each term)

= a^a(1 + 1 + 1/2 + ... + 1/a!)
< a^a*e (remembering the definition of e as 1 + 1 + 1/2! + 1/3! + 1/4! + ...)

Therefore, (a + 1)a^a/(a + 1)^a > (a + 1)a^a/(a^a*e) = (a + 1)/e. Noting that 2 < e < 3, for any a >= 2, (a + 1)/e > 1. Therefore, (a + 1)a^a/(a + 1)^a > 1, therefore, f(a)/f(a + 1) > 1, therefore, f(a) > f(a + 1) for any a >= 2.

Now we combine our three results: f(2) = 2; f is never equal to 1; and f is strictly decreasing. For any other solution to the original equation, we would have to find some z > 2 for which f(z) is a positive integer, but this integer would have to be less than 2 by the first and third results, and it can't be 1 by the second result, so we've run out of positive integers. There are no more solutions.

Therefore, all the solutions in N*×N*×N* to the original equation are:
x = 1; (y and z unrestricted)
z = 1; (x and y unrestricted)b
y = 2, z = 2. (x unrestricted).

CrystyB, I'm sure your method was more elegant than mine, but I had fun anyway.

[CrystyB]

i knew there was a reason i wouldn't like being a teacher! (besides my psychological abilities)

if you say the f has "domain N*", why "z = 1, which is definitely not true"? The rest is worthy of immortalisation.

[This message has been edited by CrystyB (edited 06-25-2003 01:01 AM).]

[Bicho the Inhaler]

CrystyB - You're right, that's not correct. The domain is supposed to be positive integers >= 2 (I said "Now suppose z > 1" and then miswrote the domain). In fact, there's no way z = 1 could be in the domain because we divide by z - 1 in the exponent. That's actually what I was thinking when I wrote "definitely not true": I just saw the 1/(z - 1) in the expression and thought "contradiction."

[Bicho the Inhaler]

Heh. I don't know how many more times I'll get to use the fact that e < 3 in a proof.

Anyway, CrystyB, I hope you don't mind if I submit a problem. I saw this posted a while ago on the Straight Dope Message Board, and it is also posed as an exercise somewhere in Rudin's Principles of Mathematical Analysis. It's a nice little problem, IMO.

Let f be continuous and differentiable on the nonnegative reals. If

1) f' is increasing on the positive reals, and
2) f(0) = 0

Prove that the function g(x) := f(x)/x is increasing on the positive reals.

[Vinny]

Hey, i have a quick question for you math type.

Let's say I borrowed $1000 from a bank (Face Value). And the interest rate is 15% for a duration of 18 months.

That means that the interest I owed is $1000 x .15 x 1.5 = $225.

And what I actually get is $775 (not $1000). This is fine if I only needed $775, but what if I needed $1000?

How do I calculate the initial face value if I were given

a) How much I need ($1000)
b) interest rate (.15)
c) duration (18 months)

?

[Vinny]

nm, i figured it out.

[Vinny]

Dang, my solution only worked if the amount of interest owed is less than the amount I needed. It get's negative and all confusing if the interest rate or duration gets too high.

Someone help me out?

[extropalopakettle]

I think there's information missing, and your math is wrong.

quote:

---

Let's say I borrowed $1000 from a bank (Face Value). And the interest rate is 15% for a duration of 18 months.

That means that the interest I owed is $1000 x .15 x 1.5 = $225

---

I assume you're multiplying by 1.5 because it's one and a half years. But how often is interest compounded? Compounded annualy, after one year you'd owe $1150. After that, you're paying interest on $1150, not on $1000. If it's 15% compounded quarterly, then every three months you owe 15%/4 = 3.75% more than what you owed three months before. The more frequently it's compounded, the more you owe (but there's a limit).

Next problem: You can't just subtract the interest you would pay on $1000 to get the amount you would borrow to end up paying $1000 at that rate. If the total accumulated interest you would pay is X%, then you'll owe 1+(X/100) times what you borrowed. So if you want to end up owing D (for debt), divide D by 1+(X/100) to get the amount you'd borrow.

For instance, if you're going to end up paying 20% (over the life of the loan), and want to end up owing $1000, then you'd borrow $1000/1.2 or $833.33. You don't subtract 20% of $1000.

[Vinny]

How about if I don't care how much I end up owing, I just need $1000. So the amount I actually borrowed (amount needed plus interest), call it FaceValue, would be higher than $1000. I need a formula to figure that out.

i.e. Given Amount Needed ($1000), InterestRate (.15), and Duration (18 months), how do I get the FaceValue that will give me $1000.

I thought the formula is

FaceValue - (FaceValue * InterestRate * Duration) = Amount Needed

and I can solve the formula for FaceValue. But things get weird if InterestRate * Duration is higher than 1.

[mathgrant]

A problem from the Putnam Exam:

Let f be a function with continuous third derivative. Prove that there exists a real number a such that

f(a)*f'(a)*f''(a)*f'''(a)>0.

[Bicho the Inhaler]

Okay.

Suppose what you say is false. Then the negation must be true, i.e., for all real a, f(a)f'(a)f''(a)f'''(a) < 0.

1) None of f, f', f'', or f''' can ever change sign on the real line, i.e., each one is either always positive or always negative. This is because all of f, f', f'', and f''' are continuous (we are given that f''' is continuous, and differentiability implies continuity for the other three), so the intermediate value theorem on the real line implies that if for any one of the four (call it g), there are two real numbers b and c for which g(b) > 0 and g(c) < 0, there must be some a between b and c for which g(a) = 0, since 0 is between g(b) and g(c). However, none of the four functions can ever be 0, because if any one is 0 at some point a, then the product

f(a)f'(a)f''(a)f'''(a) = 0 > 0,

contradicting our assumption that the proposition was false. Therefore, each one of f, f', f'', and f''' is either always positive or always negative.

2) Suppose f'' is positive for some real argument. By the previous observation, f'' is always positive. This means that f' is monotonically increasing on the real line. Now look at f'. If f'(x) = A > 0 for some x, then since f' is monotonically increasing, for y > x, f(y) > f(x) + A(y - x), so if y > x - f(x)/A, then f(y) > 0, so f > 0 everywhere. On the other hand, suppose f'(x) = B < 0 for some x. In this case, since f' is monotonically increasing, for y < x, f(y) > f(x) + B(y - x), so if y < x - f(x)/B, f(y) > 0, so f > 0 everywhere. (The inequalities I used to get this can easily be derived using the fundamental theorem of the calculus, but because I think they're fairly clear anyway, I'm omitting the proofs.) In both cases, we see that if f'' > 0, then f > 0.

If f'' < 0, apply the above argument to -f, -f', and -f'' to see that -f > 0 everywhere, i.e., f < 0 everywhere. Thus, in all cases, f and f'' must have the same sign everywhere. Therefore, f(x)f''(x) > 0 for all real x.

Now, by the above result, f'(x)f'''(x) > 0 for all real x, as well (because the above argument is a lemma that applies equally well to both f and f' here). But this is a contradiction, because it implies that

f(x)f''(x)f'(x)f'''(x) > 0, so
f(x)f'(x)f''(x)f'''(x) > 0,

contradicting our assumption that the product was always negative. Therefore, for some real a,

f(a)f'(a)f''(a)f'''(a) > 0,

which was to be shown.

[Interest]

But Vinny, you would loan exactly $1000. The interest is what you'd pay ABOVE when returning the sum. Until the deadline you'd have full use of the $1000... And extro is right about compounding the interest. Over 18 periods of a month (which is pretty common for interest computing IMO), you'd owe $1250.5774...

PS Bicho, this thread is for math, not for me showing off as good at it...

CrystyB, but i can't log on here and now

[mathgrant]

A very simple problem I made up.

Let there be infinitely many languages L₁, L₂, L₃, . . . L_n, . . . . Each language consists of D's and S's.

S is a phrase in L₁.

If x is a phrase in L_n, then xS is in L_n+1.

If Sx is a phrase in L_n, so is Dx.

If xDSSy is a phrase in L_n, so is xSDy.

In what language would you find the phrase SDDSSSDDDDSSSSSDDDDDD?

[This message has been edited by mathgrant (edited 10-02-2003 06:41 PM).]

[ChienFou]

Let x= 0.999999....
Then 10x= 9.999999999...

therefore 9x=9, all the surreal nonsense is a waste of time.

[math geek]

mg, am i to assume that L₁ consists only of S and D?

[Lucky Wizard]

I couldn't figure it out when you first posted it, but I think I've figured it out now.

Quick question: Is it safe to assume that the logical converse of those three statements is true? If so, then I think the answer is [Language 11583].

[math geek]

yes, if all the L_n sets are to be created only by the given rules, you're right, in both statements.
...and to think i was going to determine all the L_n sets! i would've had to reach 11583'rd iteration!!

[Hitchhiker]

Bump